30分

#include<bits/stdc++.h>
using namespace std;
int n,m,b[1005][1005],cnt,minn=99999999,fi_x,fi_y;
char a[1005][1005];
int cf[15]={0,1,2,4,8,16,32,64,128,256,512};
bool is_cf(int z){
    for(int i=1;i<=10;i++){
        if(z==cf[i])return 1;
    }
    return 0;
}
void dfs(int x,int y){
    if(cnt>=minn)return;
    if(a[x][y]=='#'){
        minn=min(minn,cnt);
        return;
    }
    for(int i=1;;i++){
        if(x-i<=0||a[x-i][y]=='X')break;
        if(b[x-i][y]==0&&is_cf(i)){
            b[x-i][y]=1;
            cnt++;
            dfs(x-i,y);
            b[x-i][y]=0;
            cnt--;
        }
    }
    for(int i=1;;i++){
        if(y-i<=0||a[x][y-i]=='X')break;
        if(b[x][y-i]==0&&is_cf(i)){
            b[x][y-i]=1;
            cnt++;
            dfs(x,y-i);
            b[x][y-i]=0;
            cnt--;
        }
    }
    for(int i=1;;i++){
        if(y+i>m||a[x][y+i]=='X')break;
        if(b[x][y+i]==0&&is_cf(i)){
            b[x][y+i]=1;
            cnt++;
            dfs(x,y+i);
            b[x][y+i]=0;
            cnt--;
        }
    }
    for(int i=1;;i++){
        if(x+i>n||a[x+i][y]=='X')break;
        if(b[x+i][y]==0&&is_cf(i)){
            b[x+i][y]=1;
            cnt++;
            dfs(x+i,y);
            b[x+i][y]=0;
            cnt--;
        }
    }
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=m;j++){
	        cin>>a[i][j];
	        if(a[i][j]=='#')fi_x=i,fi_y=j;
        }
    }
    if(a[1][1]=='#'){
            cout<<0;
            return 0;
        }
    b[1][1]=1;
    dfs(1,1);
    cout<<minn; 
	return 0;
}