#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair using namespace std; typedef long long ll; const int maxn=1e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m; int T[20][20]; bool vis[20][20]; bool tg[20][20]; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; bool chk(int st2){ up(i,1,n)up(j,1,m)vis[i][j]=tg[i][j]=0; down(i,n,1)down(j,m,1){if(st2&1)vis[i][j]=1;st2>>=1;} int px=0,py=0; up(i,1,n)up(j,1,m)if(vis[i][j])px=i,py=j; tg[px][py]=1; queue<pi>q; q.push(m_p(px,py)); while(!q.empty()){ int x=q.front().p1,y=q.front().p2;q.pop(); up(i,0,3){ int nx=x+dx[i],ny=y+dy[i]; if(nx<1||nx>n||ny<1||ny>m||(!vis[nx][ny])||tg[nx][ny])continue; tg[nx][ny]=1,q.push(m_p(nx,ny)); } } up(i,1,n)up(j,1,m)if((!tg[i][j])&&vis[i][j])return 0; return 1; } int dis[1<<15]; void bfs(int u){ memset(dis,-1,sizeof(dis)); queue<int>q;q.push(u);dis[u]=0; vector<int>P; up(i,1,(1<<(n*m))-1)if(chk(i))P.p_b(i); while(!q.empty()){ int u=q.front();q.pop(); for(int i:P){ if(dis[(u^i)|i]==-1)dis[(u^i)|i]=dis[u]+1,q.push((u^i)|i); if(dis[(u^i)&i]==-1)dis[(u^i)&i]=dis[u]+1,q.push((u^i)&i); } } } void slv(){ n=read(),m=read(); if(n==1||m==1){ string s; up(i,1,n){string t;cin>>t;s=s+t;} int cnt=0; up(i,0,n*m-1){ int j=i; while(j<n*m&&s[i]==s[j])j++; cnt++,i=j-1; } if(cnt%2==0||s[0]=='0')printf("%d\n",cnt/2); else printf("%d\n",(cnt+1)/2); return; } int x=0;up(i,1,n){string s;cin>>s;up(j,1,m)x=(x<<1)+s[j-1]-'0';} bfs(0);cout<<dis[x]; } int main(){ //freopen("draw.in","r",stdin); //freopen("draw.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }