// subtask 1,2 // 10pts #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 201; int n, m, a[N][N]; namespace Sub2 { vector<pair<int, int> > zero; int lim, cnt0, ok, vis[N][N], ans; void put(int x, int y) { for (int i = x; i >= 1; i--) { if (a[i][y]) break; if (!vis[i][y]++) cnt0--; } for (int i = x; i <= n; i++) { if (a[i][y]) break; if (!vis[i][y]++) cnt0--; } for (int i = y; i >= 1; i--) { if (a[x][i]) break; if (!vis[x][i]++) cnt0--; } for (int i = y; i <= m; i++) { if (a[x][i]) break; if (!vis[x][i]++) cnt0--; } } void erase(int x, int y) { for (int i = x; i >= 1; i--) { if (a[i][y]) break; if (!--vis[i][y]) cnt0++; } for (int i = x; i <= n; i++) { if (a[i][y]) break; if (!--vis[i][y]) cnt0++; } for (int i = y; i >= 1; i--) { if (a[x][i]) break; if (!--vis[x][i]) cnt0++; } for (int i = y; i <= m; i++) { if (a[x][i]) break; if (!--vis[x][i]) cnt0++; } } void dfs2(int u, int cnt) { if (ok) return; if (!cnt0) { ok = 1; return; } if (cnt == lim) return; for (int i = u; i < zero.size(); i++) { pair<int, int> p = zero[i]; if (vis[p.first][p.second]) continue; put(p.first, p.second); dfs2(i + 1, cnt + 1); erase(p.first, p.second); } } void dfs1(int x, int y) { if (y > m) { if (x < n) dfs1(x + 1, 1); else { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { vis[i][j] = 0; } } cnt0 = zero.size(), lim = ok = 0; while (lim < ans) { dfs2(0, 0); if (ok) break; lim++; } if (ok) ans = min(ans, lim); // for (int i = 1; i <= n; i++) { // for (int j = 1; j <= m; j++) { // cout << a[i][j] << ' '; // } // cout << endl; // } // cout << lim << endl << endl; } return; } if (a[x][y] != 2) dfs1(x, y + 1); else { a[x][y] = 0, zero.push_back(make_pair(x, y)); dfs1(x, y + 1); zero.pop_back(); a[x][y] = 1; dfs1(x, y + 1); a[x][y] = 2; } } int Main() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (!a[i][j]) zero.push_back(make_pair(i, j)); } } ans = 0x7FFFFFFF; dfs1(1, 1); printf("%d\n", ans); return 0; } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%1d", &a[i][j]); } } if (n == 1 && m == 1) { printf("%d\n", (int)(a[1][1] == 0)); fclose(stdin); fclose(stdout); return 0; } Sub2::Main(); return 0; }