30分

#include<bits/stdc++.h>
using namespace std;
int n,m,fi_x,fi_y,xx,yy,b[1005][1005],cnt,bs[1005][1005];
char a[1005][1005];
queue<int>x;
queue<int>y;
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;
    x.push(1);
    y.push(1);
    while(1){
        xx=x.front(),yy=y.front();
        if(xx==fi_x&&yy==fi_y){
            cout<<bs[fi_x][fi_y];
            return 0;
        }
        cnt=1;
        for(int i=1;;i++){
            if(xx-i>0&&a[xx-i][yy]!='X'){
                if((i==1||float(i*1.0/cnt)==2)&&b[xx-i][yy]==0){
                    cnt*=2;
                    x.push(xx-i);
                    y.push(yy);
                    if(bs[xx-i][yy]==0)bs[xx-i][yy]=bs[xx][yy]+1;
                    else bs[xx-i][yy]=min(bs[xx][yy]+1,bs[xx-i][yy]);
                    b[xx-i][yy]=1;
                    if(xx-i==fi_x&&yy==fi_y){
                    cout<<bs[fi_x][fi_y];
                    return 0;
                    }
                }
            }
            else break;
        }
        cnt=1;
        for(int i=1;;i++){
            if(yy-i>0&&a[xx][yy-i]!='X'){
                if((i==1||float(i*1.0/cnt)==2)&&b[xx][yy-i]==0){
                    cnt*=2;
                    x.push(xx);
                    y.push(yy-i);
                    if(bs[xx][yy-i]==0)bs[xx][yy-i]=bs[xx][yy]+1;
                    else bs[xx][yy-i]=min(bs[xx][yy]+1,bs[xx][yy-i]);
                    b[xx][yy-i]=1;
                     if(xx==fi_x&&yy-i==fi_y){
                    cout<<bs[fi_x][fi_y];
                    return 0;
                    }
                }
            }
            else break;
        }
        cnt=1;
        for(int i=1;;i++){
            if(yy+i<=m&&a[xx][yy+i]!='X'){
                if((i==1||float(i*1.0/cnt)==2)&&b[xx][yy+i]==0){
                    cnt*=2;
                    x.push(xx);
                    y.push(yy+i);
                    if(bs[xx][yy+i]==0)bs[xx][yy+i]=bs[xx][yy]+1;
                    else bs[xx][yy+i]=min(bs[xx][yy]+1,bs[xx][yy+i]);
                    b[xx][yy+i]=1;
                     if(xx==fi_x&&yy+i==fi_y){
                    cout<<bs[fi_x][fi_y];
                    return 0;
                    }
                }
            }
            else break;
        }
        cnt=1;
        for(int i=1;;i++){
            if(xx+i<=n&&a[xx+i][yy]!='X'){
                if((i==1||float(i*1.0/cnt)==2)&&b[xx+i][yy]==0){
                    cnt*=2;
                    x.push(xx+i);
                    y.push(yy);
                    if(bs[xx+i][yy]==0)bs[xx+i][yy]=bs[xx][yy]+1;
                    else bs[xx+i][yy]=min(bs[xx][yy]+1,bs[xx+i][yy]);
                    b[xx+i][yy]=1;
                     if(xx+i==fi_x&&yy==fi_y){
                    cout<<bs[fi_x][fi_y];
                    return 0;
                    }
                }
            }
            else break;
        }
        x.pop(),y.pop();
        if(x.empty()==-1){
            cout<<-1;
            return 0;
        }
    }
	return 0;
}