#include #include #include struct T { int x, y; }; std::queue Q; const int dx[] = {0, 1, -1, 0}; const int dy[] = {1, 0, 0, -1}; int n, m, cnt, ans, M[9][9], N[9][9]; bool visited[9][9]; //안에 있는 점인지 체크 bool inside(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; } //bfs void bfs() { //M을 N으로 복사, 2인 것을 큐에 집어넣기 for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (M[i][j] == 2) Q.push({i, j}); N[i][j] = M[i][j]; } } //본격적인 bfs while (!Q.empty()) { T tmp = Q.front(); Q.pop(); for (int i = 0; i < 4; i++) { int tx = dx[i] + tmp.x, ty = dy[i] + tmp.y; if (N[tmp.x][tmp.y] == 2 && inside(tx, ty) && N[tx][ty] == 0) { N[tx][ty] = 2; Q.push({tx, ty}); } } } //다 퍼지고 나서 안전한 칸 수 체크 int chk = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (M[i][j] == 0) chk++; ans = std::max(ans, chk); return; } //벽 세우기 void solve(int x, int y, int dpt) { if (dpt == 3) { bfs(); return; } if (inside(x, y) && M[x][y] == 0 && !visited[x][y]) { M[x][y] = 1; visited[x][y] = 1; solve(x + 1, y, dpt + 1); solve(x, y + 1, dpt + 1); M[x][y] = 0; visited[x][y] = 0; } return; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", M[i] + j); solve(0, 0, 0); printf("%d", ans); return 0; } /*#include #include const int dx[] = {0, 1, -1, 0, 1, 1, -1, -1}; const int dy[] = {1, 0, 0, -1, 1, -1, 1, -1}; int T, n, m, k, M[51][51], ans; bool inside(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; } void solve(int x, int y) { M[x][y] = ans; for (int i = 0; i < 8; i++) { int tx = x + dx[i], ty = y + dy[i]; if (inside(tx, ty) && M[tx][ty] == 1) { M[tx][ty] = ans; solve(tx, ty); } } } int main() { while (true) { memset(M, 0, sizeof(M)); ans = 2; scanf("%d%d", &n, &m); if (n == 0 && m == 0) break; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) scanf("%d", M[i] + j); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (M[i][j] == 1) { solve(i, j); ans++; } } } printf("%d\n", ans - 2); } return 0; } /*#include #include const int dx[] = {0, 1, -1, 0}, dy[] = {1, 0, 0, -1}; int N, mh, ans, M[101][101]; bool visited[101][101]; bool inside(int x, int y, int l) { return x >= 0 && x < N && y >= 0 && y < N && M[y][x] > l; } void dfs(int x, int y, int l) { visited[y][x] = true; for (int i = 0; i < 4; i++) { int tx = x + dx[i], ty = y + dy[i]; if (inside(tx, ty, l) && !visited[ty][tx]) dfs(tx, ty, l); } return; } int main() { scanf("%d", &N); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) scanf("%d", &M[i][j]); for (int k = 0; k <= 100; k++) { int cnt = 0; memset(visited, 0, sizeof(visited)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (M[i][j] > k && !visited[i][j]) { cnt++; dfs(j, i, k); } } } if (cnt > ans) ans = cnt; if (cnt == 0) break; } printf("%d", ans); return 0; } /*#include #include #include const int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1}; const int dy[] = {2, 1, -1, -2, -2, -1, 1, 2}; struct TT { int x, y, n; }; std::queue Q; int T, I, x1, y1, x2, y2; bool visited[301][301]; bool inside(int x, int y) { return 0 <= x && x < I && 0 <= y && y < I; } int main() { scanf("%d", &T); while (T--) { while (!Q.empty()) Q.pop(); memset(visited, 0, sizeof(visited)); scanf("%d%d%d%d%d", &I, &x1, &y1, &x2, &y2); Q.push({x1, y1, 0}); visited[x1][y1]; while (!Q.empty()) { TT tmp = Q.front(); Q.pop(); if (tmp.x == x2 && tmp.y == y2) { printf("%d\n", tmp.n); break; } for (int i = 0; i < 8; i++) { int tx = tmp.x + dx[i], ty = tmp.y + dy[i]; if (inside(tx, ty) && !visited[tx][ty]) { visited[tx][ty] = 1; Q.push({tx, ty, tmp.n + 1}); } } } } return 0; } /*#include #include #include struct T { int x, y, N; }; int ans, m, n, M[1001][1001]; const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}; bool inside(int x, int y) { return 0 <= x && x < m && 0 <= y && y < n; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) scanf("%d", M[i] + j); std::queue Q; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (M[i][j] == 1) Q.push({i, j, 0}); while (!Q.empty()) { T tmp = Q.front(); Q.pop(); ans = std::max(ans, tmp.N); for (int i = 0; i < 4; i++) { int tx = tmp.x + dx[i], ty = tmp.y + dy[i]; if (inside(tx, ty) && !M[tx][ty]) { Q.push({tx, ty, tmp.N + 1}); M[tx][ty] = 1; } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (!M[i][j]) { printf("-1"); return 0; } } } printf("%d", ans); return 0; } /*#include #include #define INF 987654321 int N, DT[100001]; int solve(int i) { if (i == 0) return 0; if (DT[i] != INF) return DT[i]; for (int j = 1; j * j <= i; j++) DT[i] = std::min(solve(i - j * j) + 1, DT[i]); return DT[i]; } int main() { scanf("%d", &N); for (int i = 0; i <= N; i++) DT[i] = INF; for (int i = 1; i * i <= N; i++) DT[i * i] = 1; printf("%d\n", solve(N)); return 0; } /*#include #include #include int N, K, V[10001], DT[101][1001]; int solve(int i, int v) { if (v < 0) return 0; if (v == 0) return 1; if (i == N) return 0; if (DT[i][v]) return DT[i][v]; for (int j = 0; j <= v / V[i]; j++) DT[i][v] += solve(i + 1, v - V[i] * j); return DT[i][v]; } int main() { scanf("%d %d", &N, &K); for (int i = 0; i < N; i++) scanf("%d", V + i); std::sort(V, V + N, std::less()); printf("%d", solve(0, K)); return 0; } /*#include #include #include struct T { int x, y, dst; }; const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}; int N, M, ans = 987654321, mz[101][101]; bool visited[101][101], flag; std::queue Q; bool is_inside(int x, int y) { return 0 <= x && x < N && 0 <= y && y < M; } void solve() { Q.push({0, 0, 1}); while (!Q.empty()) { T tmp = Q.front(); Q.pop(); if (tmp.x == N - 1 && tmp.y == M - 1) ans = std::min(ans, tmp.dst); for (int i = 0; i < 4; i++) { int tx = tmp.x + dx[i], ty = tmp.y + dy[i]; if (!visited[tx][ty] && is_inside(tx, ty) && mz[tx][ty]) { visited[tx][ty] = 1; Q.push({tx, ty, tmp.dst + 1}); } } } return; } int main() { scanf("%d%d", &N, &M); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) scanf("%1d", mz[i] + j); solve(); printf("%d", ans); return 0; } /*#include long long int fibo[1000001]; int main() { fibo[0] = 0; fibo[1] = 1; for (int i = 2; i < 1000001; i++) fibo[i] = fibo[i - 1] + fibo[i - 2]; int n; scanf("%d", &n); printf("%lld", fibo[n]); return 0; } /*#include int a, b; int gcd(int x, int y) { if (x < y) { int tmp = x; x = y; y = tmp; } if (x == y) return x; if (!y) return x; return gcd(y, x % y); } int main() { scanf("%d%d", &a, &b); printf("%d\n%d", gcd(a, b), a * b / gcd(a, b)); return 0; } /*#include #include int k, S[13]; bool visited[50]; void solve(int i, int b, std::vector V) { if (i == 6) { for (int j = 0; j < 6; j++) printf("%d ", V[j]); puts(""); return; } for (int j = b; j < k; j++) { if (!visited[j]) { std::vector tmp; for (int l = 0; l < i; l++) tmp.push_back(V[l]); tmp.push_back(S[j]); visited[j] = 1; solve(i + 1, j, tmp); visited[j] = 0; } } } int main() { while (true) { scanf("%d", &k); if (!k) return 0; for (int i = 0; i < 50; i++) visited[i] = 0; for (int i = 0; i < k; i++) scanf("%d", S + i); std::vector tmp; solve(0, 0, tmp); puts(""); } return 0; }*/