#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fi first #define se second #define mp make_pair int n,m; char a[200][200]; pii pos[100010],ava[100010]; int c; int tot; int minn; int used[100010],vis[200][200],stat[100010]; void calc(int p,int cnt) { if(cnt>=minn) return ; if(p>c) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]=='0'&&vis[i][j]==0) return ; minn=cnt; return ; } stat[p]=1; int x=ava[p].fi,y=ava[p].se; int pos=x; while(pos>0) { if(a[pos][y]=='1') break; vis[pos][y]++; pos--; } pos=x; while(pos<=n) { if(a[pos][y]=='1') break; vis[pos][y]++; pos++; } pos=y; while(pos>0) { if(a[x][pos]=='1') break; vis[x][pos]++; pos--; } pos=y; while(pos<=m) { if(a[x][pos]=='1') break; vis[x][pos]++; pos++; } calc(p+1,cnt+1); pos=x; while(pos>0) { if(a[pos][y]=='1') break; vis[pos][y]--; pos--; } pos=x; while(pos<=n) { if(a[pos][y]=='1') break; vis[pos][y]--; pos++; } pos=y; while(pos>0) { if(a[x][pos]=='1') break; vis[x][pos]--; pos--; } pos=y; while(pos<=m) { if(a[x][pos]=='1') break; vis[x][pos]--; pos++; } stat[p]=0; calc(p+1,cnt); } int ans=1e9; void dfs(int p) { if(p>tot) { for(int i=1;i<=tot;i++) { int x=pos[i].fi,y=pos[i].se; if(used[i]) a[x][y]='0'; else a[x][y]='1'; } minn=1e9,c=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]=='0') ava[++c]={i,j}; calc(1,0); ans=min(ans,minn); for(int i=1;i<=tot;i++) if(used[i]) { int x=pos[i].fi,y=pos[i].se; a[x][y]='2'; } return ; } used[p]=1; dfs(p+1); used[p]=0; dfs(p+1); } int main() { // freopen("daredevil.in","r",stdin); // freopen("daredevil.out","w",stdout); ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]+1; if(n*m==1) { if(a[1][1]=='0') cout<<1<<endl; else cout<<0<<endl; return 0; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]=='2') pos[++tot]=mp(i,j); dfs(1); cout<<ans<<endl; return 0; }