#include<iostream>
#include<queue> 
using namespace std;
const int N=2e3+7;

int n,m;
int ma[N][N],vis[N][N];
int su1[N][N],su2[N][N];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
struct st{
    int x,y,v;
};

int bfs(){
    if(ma[1][1]==1||ma[n][m]==1)return -1;
    queue<st>q;
    q.push({1,1,0});
    while(!q.empty()){
        st t=q.front();
        if(t.x==n&&t.y==m)return t.v;
        q.pop();
        if(vis[t.x][t.y])continue;
        vis[t.x][t.y]=1;
        for(int i=0;((1<<i)+t.x)<=n;i++)
            if(!vis[(1<<i)+t.x][t.y]&&(su1[(1<<i)+t.x][t.y]-su1[t.x-1][t.y])==0){
                if((1<<i)+t.x==n&&t.y==m)return t.v+1;
                q.push({(1<<i)+t.x,t.y,t.v+1});
            }
        for(int i=0;(t.x-(1<<i))>=1;i++)
            if(!vis[t.x-(1<<i)][t.y]&&(su1[t.x][t.y]-su1[t.x-(1<<i)-1][t.y])==0){
                if(t.x-(1<<i)==n&&t.y==m)return t.v+1;
                q.push({t.x-(1<<i),t.y,t.v+1});
            }
        for(int i=0;((1<<i)+t.y)<=m;i++)
            if(!vis[t.x][(1<<i)+t.y]&&(su2[t.x][(1<<i)+t.y]-su2[t.x][t.y-1])==0){
                if(t.x==n&&(1<<i)+t.y==m)return t.v+1;
                q.push({t.x,(1<<i)+t.y,t.v+1});
            }
        for(int i=0;(t.y-(1<<i))>=1;i++)
            if(!vis[t.x][t.y-(1<<i)]&&(su2[t.x][t.y]-su2[t.x][t.y-(1<<i)-1])==0){
                if(t.x==n&&t.y-(1<<i)==m)return t.v+1;
                q.push({t.x,t.y-(1<<i),t.v+1});
            }
    }
    return -1;
}
int main( ){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>ma[i][j];
            su1[i][j]=su1[i-1][j]+ma[i][j];
            su2[i][j]=su2[i][j-1]+ma[i][j];
        }
    cout<<bfs()<<endl;
    return 0;
}

0 comments

No comments so far...