SWEA 2117 홈 방범 서비스

코드:

/* 1. 좌표 행열 상한 모두 N */
/* 2. 전역변수 초기화 */
/* 3. 안 돌아가는 TC 파악하기 같은 특성의 작은 TC 만들어서 해보는 것도 중요 */
/* 4. 정답 판별 중간에만 하지 말고 끝에도 해줄 것 */

#include <iostream>
#include <queue>

using namespace std;

int T;
int N, M;
bool map[20][20];
int vst[20][20];
int v = 1;
int ans;

int dn[] = { -1, 0, 1, 0 };
int dm[] = { 0, 1, 0, -1 };

#define IN(n, m) (0 <= (n) && (n) < N && 0 <= (m) && (m) < N)	/* 1 */

struct qnode {
	int n, m, l;
};

void BFS(int rn, int rm) {
	vst[rn][rm] = v;
	queue<qnode> q;
	q.push({ rn, rm, 1 });

	int lvl = 1, cst = 1, hh = 0;
	while (!q.empty()) {
		qnode pt = q.front(); q.pop();

		if (pt.l > lvl) {
			if (cst <= hh * M && hh > ans)
				ans = hh;

			cst += lvl * 4;
			lvl = pt.l;
		}

		if (map[pt.n][pt.m])
			++hh;

		for (int d = 0; d < 4; ++d) {
			int cn = pt.n + dn[d], cm = pt.m + dm[d];
			if (IN(cn, cm) && vst[cn][cm] != v) {
				vst[cn][cm] = v;
				q.push({ cn, cm, pt.l + 1 });
			}
		}
	}
	if (cst <= hh * M && hh > ans)	/* 3 */	/* 4 */
		ans = hh;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> T;
	for (int t = 1; t <= T; ++t) {
		cin >> N >> M;
		for (int n = 0; n < N; ++n) {
			for (int m = 0; m < N; ++m) {
				cin >> map[n][m];
			}
		}

		ans = 0;	/* 2 */

		for (int n = 0; n < N; ++n) {
			for (int m = 0; m < N; ++m) {
				++v;
				BFS(n, m);
			}
		}

		cout << '#' << t << ' ' << ans << '\n';
	}

	return 0;
}