글 읽기 - 반례가 더 있을까요?

ds04030 4년 전 0

tc와 질문 게시판에 나와있는 반례를 모두 돌려봤는데 맞았습니다.

근데 제출하면 틀렸다고 하네요.. 혹시 또다른 반례가 더 있을까요?

혹시 제가 놓친 부분이 있다면 알려주시면 감사하겠습니다..!

/*
	캐슬 디펜스
*/

#include <iostream>
using namespace std;

int N, M, D;
int map[16][16];
int Map[16][16];
void copyMap();
void solve();
int go(int a, int b, int c);
int result = 0;
int isDistance(int x, int y, int r, int c) {
	int ret = abs(x - r) + abs(y - c);
	if (ret <= D) return ret;
	else return 9999;
}

int main()
{
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	cout << result << "\n";
	return 0;
}

void solve() {
	for (int j = 0; j < M - 2; j++) {
		for (int k = j + 1; k < M - 1; k++) {
			for (int l = k + 1; l < M; l++) {
				copyMap();
				int ret = go(j, k, l);
				if (ret > result) result = ret;
				//cout << "(" << j << "  " << k << "   " << l << "):" << ret << "\n";
			}
		}
	}

	
}

void copyMap() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			Map[i][j] = map[i][j];
		}
	}
}

int go(int a, int b, int c) {
	int ret = 0;
	int depth = 0;
	while (N - depth > 0) {
		int ax = 9999, ay = 9999, bx = 9999, by = 9999, cx = 9999, cy = 9999;
		int ad = 9999, bd = 9999, cd = 9999;
		bool canA = false, canB = false, canC = false;
		for (int i = 0; i < N - depth; i++) {
			for (int j = 0; j < M; j++) {
				if (Map[i][j] == 0) continue;

				int d1 = isDistance(N, a, i + depth, j);
				if (d1 <= D) {
					if ((d1 < ad) || (d1==ad && j<ay)) {
						ax = i, ay = j;
						canA = true;
						ad = d1;
					}
					
				}

				int d2 = isDistance(N, b, i + depth, j);
				if (d2 <= D) {
					if ((d2 < bd) || (d2 == bd && j<by)) {

						bx = i, by = j;
						canB = true;
						bd = d2;
					}

				}

				int d3 = isDistance(N, c, i + depth, j);
				if (d3 <= D) {
					if ((d3 < cd) || (d3 == cd && j<cy)) {
						cx = i, cy = j;
						canC = true;
						cd = d3;
					}

				}

			}
		}

		//cout << "[Deapth" << depth + 1 << "]";
		if (canA) {
			Map[ax][ay] = 0;
			//cout << "A:" << ax << "," << ay << "   ";
		}

		if (canB) {
			Map[bx][by] = 0;
			//cout << "B:" << bx << "," << by << "   ";
		}

		if (canC) {
			Map[cx][cy] = 0;
			//cout << "C:" << cx << "," << cy << "   ";
		}

		if (canA && canB && canC && (ax != bx || ay != by) && (bx != cx || by != cy) && (ax != cx || ay != cy)) {
			ret += 3;
		}
		else if (canA && canB && (ax != bx || ay != by)) {
			ret += 2;
		}
		else if (canB && canC && (bx != cx || by != cy)) {
			ret += 2;
		}
		else if (canA && canC && (ax != cx || ay != cy)) {
			ret += 2;
		}
		else if ((canA && !canB && !canC) || (!canA && canB && !canC) || (!canA && !canB && canC)) {
			ret += 1;
		}
		depth++;
	}	
	return ret;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 더 있을까요?

ds04030 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말