#include<bits/stdc++.h> using namespace std; #define int long long const int MAXN=20,inf=1000000000; int n,m,k,ans; char a[MAXN][MAXN]; int p[MAXN][MAXN]; int tim=0; void dfs2(int x,int y){ tim++; if(tim>=90000000) break; if(k>1)return; if(x==n+1){ k++; return; } int nx=x,ny=y; if(ny+1<=m)ny++; else nx++,ny=1; if(a[x][y]=='.'){ dfs2(nx,ny); return; } bool res=0; a[x][y]='.'; for(int i=x+1;i<=n;i++){ if(a[i][y]=='#'){ a[i][y]='.'; dfs2(nx,ny); a[i][y]='#'; } } for(int i=y+1;i<=m;i++){ if(a[x][i]=='#'){ a[x][i]='.'; dfs2(nx,ny); a[x][i]='#'; } } a[x][y]='#'; } void dfs(int x,int y,int sum,int num,int lim){ if(num>=ans||num>=lim||tim>=90000000)return; tim++; if(x==n+1||num==lim){ if(sum&1)return; k=0; dfs2(1,1); if(k==1)ans=num; return; } int nx=x,ny=y; if(ny+1<=m)ny++; else nx++,ny=1; if(a[x][y]=='#')dfs(nx,ny,sum+1,num,lim); else{ dfs(nx,ny,sum,num,lim); a[x][y]='#'; dfs(nx,ny,sum+1,num+1,lim); a[x][y]='.'; } } void slv(){ans=inf; scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ a[i][j]=getchar(); while(a[i][j]!='.'&&a[i][j]!='#')a[i][j]=getchar(); } } for(int lim=0;lim<=10;lim++) { dfs(1,1,0,0,lim); } printf("%lld",ans==inf?-1:ans); } signed main(){ // freopen("b.in","r",stdin); // freopen("b.out","w",stdout); slv(); return 0; }