//uh, couldnt believe i've to do this. //oh, back on the grind. //yolo, woo. //Boringgggg. #include <bits/stdc++.h> using namespace std; int n, m; char s[55][55], g[55][55]; bool vis[55][55], ss[10], nv[55][55]; int gl; const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[] = {-1, 0, 1, 1, 1, 0, -1, -1}; //const int dx[] = {0, 0, -1, -1, -1, 1, 1, 1}, dy[] = {-1, 1, -1, 0, 1, -1, 0, 1}; const int wx[] = {-1, -1, 1, 1}, wy[] = {-1, 1, -1, 1}; priority_queue <pair <int, pair <int, int> > > pq; inline void work(bool tp) { // for (int i = 1; i <= n; i++) // for (int j = 1; j <= m; j++) // nv[i][j] = 0; gl = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (vis[i][j] && g[i][j] != tp + '0' && s[i][j] == tp + '0') { g[i][j] = tp + '0'; nv[i][j] = 1; bool b = 1; for (int d = 0; d < 8; d++) { ss[d] = 0; int x = i + dx[d], y = j + dy[d]; if (x >= 1 && y >= 1 && x <= n && y <= m && vis[x][y] && g[x][y] != tp + '0' && s[x][y] == tp + '0') { g[x][y] = tp + '0'; nv[x][y] = 1; ss[d] = 1; b = 0; } } if (b) { gl++; continue; } for (int d = 0; d < 8; d += 2) { if (ss[d]) if (ss[(d + 1) % 8] || ss[(d - 1 + 8) % 8]) { ss[d] = 0; } } for (int d = 1; d < 8; d += 2) { if (ss[(d - 1 + 8) % 8] && ss[(d + 1) % 8]) { g[i + dx[d]][j + dy[d]] = tp + '0'; nv[i + dx[d]][j + dy[d]] = 1; ss[(d - 1 + 8) % 8] = ss[(d + 1) % 8] = 0; } } for (int d = 0; d < 8; d += 2) { if (ss[d]) { g[i + dx[(d + 1) % 8]][j + dy[(d + 1) % 8]] = tp + '0'; nv[i + dx[(d + 1) % 8]][j + dy[(d + 1) % 8]] = 1; } } } } } memcpy(vis, nv, sizeof vis); // for (int i = 1; i <= n; i++) // { // for (int j = 1; j <= m; j++) // { // putchar(g[i][j]); // } // putchar('\n'); // } } #define mkp make_pair queue <pair <int, int> > q; const int sx[] = {-1, 1, 0, 0}, sy[] = {0, 0, -1, 1}; inline void bfs(int x, int y) { q.push(mkp(x, y)); nv[x][y] = 0; while (!q.empty()) { x = q.front().first, y = q.front().second; q.pop(); for (int d = 0; d < 4; d++) { int nx = x + sx[d], ny = y + sy[d]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && nv[nx][ny]) { q.push(mkp(nx, ny)); nv[nx][ny] = 0; } } } } inline bool chk() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s[i][j] != g[i][j]) { return 0; } } } return 1; } signed main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%s", s[i] + 1); for (int j = 1; j <= m; j++) vis[i][j] = 1, g[i][j] = '0'; } int cnt = 0, ans = 0; while (!chk()) { // printf("round %d\n", cnt); work(++cnt & 1); int del = 0; int mx = -1, my = -1, nx = 1e2, ny = 1e2; for (int i = 1; i <= n; i++) { // printf("%s\n", g[i] + 1); for (int j = 1; j <= m; j++) { if (nv[i][j]) { bfs(i, j); del++; } if (vis[i][j]) { mx = max(mx, i); my = max(my, j); nx = min(nx, i); ny = min(ny, j); } } } int s = (mx - nx + 1) * (my - ny + 1); if (del >= s / 4.0 && n != 1) { for (int i = nx; i <= mx; i++) { for (int j = ny; j <= my; j++) { vis[i][j] = 1; g[i][j] = (cnt & 1) + '0'; nv[i][j] = 0; } } del = 1; } ans += del; // for (int i = 1; i <= n; i++) // printf("%s\n", g[i] + 1); } printf("%d", ans); return 0; }