#include<bits/stdc++.h> using namespace std; #define int long long const int MAXN=20,inf=1000000000; int n,m,k,ans,t; char a[MAXN][MAXN]; int p[MAXN][MAXN]; void dfs2(int x,int y){ // 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){ t++; if(t>=90000080)return; if(num>=ans)return; if(x==n+1){ 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); else{ dfs(nx,ny,sum,num); a[x][y]='#'; dfs(nx,ny,sum+1,num+1); 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(); } } dfs(1,1,0,0); printf("%lld",ans==inf?-1:ans); } signed main(){ slv(); return 0; }