#include<bits/stdc++.h>
using namespace std;
#define up(i,l,r) for(int i=l;i<=r;++i)
#define dn(i,l,r) for(int i=l;i>=r;--i)
const int N=1005;
char c[N][N];
int s[N][N][3]; 
int dp[N][N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n,m;
	cin>>n>>m;
	up(i,1,n){
		up(j,1,m){
			cin>>c[i][j];
		}
	} 
	up(i,1,n){
		up(j,1,m){
			if(c[i][j]=='.'||c[i][j]=='$'){
				s[i][j][0]=s[i-1][j][0];
			}else{
				s[i][j][0]=s[i-1][j][0]+1;
			}
		}
	}
	up(i,1,m){
		up(j,1,n){
			if(c[j][i]=='.'||c[j][i]=='$'){
				s[i][j][1]=s[i][j-1][1];
			}else{
				s[i][j][1]=s[i][j-1][1]+1;
			}
		}
	}
	queue<pair<int,int> > q;
	q.push({1,1});
	up(i,1,n) up(j,1,m) dp[i][j]=1e9;
	dp[1][1]=0;
	while(q.size()){
		int x=q.front().first;
		int y=q.front().second;q.pop();
		up(i,0,9){
			//left
			if(y>(1<<i)){
				if(c[x][y-(1<<i)]=='#'&&(s[x][y][0]-s[x][y-(1<<i)+1][0]==0)){
					if(dp[x][y-(1<<i)]>dp[x][y]+1){
						dp[x][y-(1<<i)]=dp[x][y]+1;
						q.push({x,y-(1<<i)});
					}
				}
				if(s[x][y][0]-s[x][y-(1<<i)][0]==0){
					if(dp[x][y-(1<<i)]>dp[x][y]+1){
						dp[x][y-(1<<i)]=dp[x][y]+1;
						q.push({x,y-(1<<i)});
					}
				}
			} 
			//right
			if(y+(1<<i)<=m){
				if(c[x][y+(1<<i)]=='#'&&(s[x][y+(1<<i)-1][0]-s[x][y][0]==0)){
					if(dp[x][y+(1<<i)]>dp[x][y]+1){
						dp[x][y+(1<<i)]=dp[x][y]+1;
						q.push({x,y+(1<<i)});
					}
				}
				if(s[x][y+(1<<i)][0]-s[x][y][0]==0){
					if(dp[x][y+(1<<i)]>dp[x][y]+1){
						dp[x][y+(1<<i)]=dp[x][y]+1;
						q.push({x,y+(1<<i)});
					}
				}
			} 
			if(x-(1<<i)>0){
				if(c[x-(1<<i)][y]=='#'&&(s[y][x][1]-s[y][x-(1<<i)+1][1]==0)){
					if(dp[x-(1<<i)][y]>dp[x][y]+1){
						dp[x-(1<<i)][y]=dp[x][y]+1;
						q.push({x-(1<<i),y});
					}
				}
				if(s[y][x][1]-s[y][x-(1<<i)][1]==0){
					if(dp[x-(1<<i)][y]>dp[x][y]+1){
						dp[x-(1<<i)][y]=dp[x][y]+1;
						q.push({x-(1<<i),y});
					}
				}
			}
			if(x+(1<<i)<=n){
				if(c[x+(1<<i)][y]=='#'&&(s[y][x+(1<<i)-1][1]-s[y][x][1]==0)){
					if(dp[x+(1<<i)][y]>dp[x][y]+1){
						dp[x+(1<<i)][y]=dp[x][y]+1;
						q.push({x+(1<<i),y});
					}
				}
				if(s[y][x+(1<<i)][1]-s[y][x][1]==0){
					if(dp[x+(1<<i)][y]>dp[x][y]+1){
						dp[x+(1<<i)][y]=dp[x][y]+1;
						q.push({x+(1<<i),y});
					}
				}
			}
		}
	}
//	up(i,1,n){
//		up(j,1,m){
//			cout<<dp[i][j]<<' ';
//		}
//		cout<<'\n';
//	}
	up(i,1,n){
		up(j,1,m){
			if(c[i][j]=='#'){
				if(dp[i][j]==1e9){
					cout<<"-1";return 0;
				}else{
					cout<<dp[i][j]<<'\n';return 0;
				}
			}
		}
	}
	return 0;
}
//tomxi