labirint2

#include <fstream>
#include <queue>
using namespace std;

int grid[1001][1001],viz[1001][1001];
int dist[2][1001][1001];

int ml[]={1,0,-1,0};
int mc[]={0,1,0,-1};

ifstream cin("labirint2.in");
ofstream cout("labirint2.out");

int n,m;

void lee(int s1,int s2,int ind){
    int cntc,i,l,c,j;
    queue<pair<int,int>>mers;
    queue<int>cnt;
    cnt.push(0);
    mers.push({s1,s2});
    viz[s1][s2]=1;
    while(!mers.empty()){
        pair<int,int> poz=mers.front();
        cntc=cnt.front();
        mers.pop();
        cnt.pop();
        for(i=0;i<4;i++){
            l=poz.first+ml[i];
            c=poz.second+mc[i];
            if(l>0 && l<=n && c>0 && c<=m && viz[l][c]==0){
                viz[l][c]=1;
                dist[ind][l][c]=cntc+1;
                if(grid[l][c]==0){
                    cnt.push(cntc+1);
                    mers.push({l,c});
                }
            }
        }
    }
    for(i=0;i<=n;i++){
        for(j=0;j<=m;j++){
            viz[i][j]=0;
        }
    }
}

int main()
{
    int i,j;
    char cha;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            cin>>cha;
            if(cha=='1')
                grid[i][j]=1;
        }

    lee(1,1,0);
    lee(n,m,1);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(grid[i][j]==1 && dist[0][i][j]>0 && dist[1][i][j]>0){
                if(dist[0][n][m]>dist[0][i][j]+dist[1][i][j]-1)
                    cout<<"1";
                else
                    cout<<"0";
            }else
                cout<<"0";
        }
        cout<<"\n";
    }
    return 0;
}