labirint5

#include <bits/stdc++.h>
using namespace std;

ifstream fin("labirint.in");
ofstream fout("labirint.out");

char ch;
int a[1001][1001], b[1001][1001], c[1001][1001];
int N, M;

void Lee(int x, int y, int a[][1001])
{

    int l[] = {-1, 1, 0, 0}, c[] = {0, 0, -1, 1};
    queue <pair <int, int>> q;
    q.push({x, y});
    a[x][y] = 2;
    while(!q.empty())
    {
        int i = q.front().first, j = q.front().second;
        q.pop();
        for(int d = 0; d < 4; d++)
        {
            int ii = i + l[d], jj = j + c[d];
            if(ii < 1 || ii > N || jj < 1 || jj > M)
                continue;

            if(a[ii][jj] == -1)
            {
                a[ii][jj] = a[i][j] + 1;
                continue;
            }

            if(a[ii][jj] == 0)
            {
                a[ii][jj] = a[i][j] + 1;
                q.push({ii, jj});
            }
        }
    }
}

int main()
{

    fin>>N>>M;
    fin.get();
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            fin>>ch;
            a[i][j] = (ch == '0')? 0 : 1, b[i][j] = c[i][j] = -a[i][j];
        }
    }
    Lee(1, 1, b);
    Lee(N, M, c);
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
            if(a[i][j] == 1 && b[i][j] + c[i][j] - 1 < b[N][M] && b[i][j] + c[i][j] - 1 >= 0)
                fout.put('1');
            else
                fout.put('0');
        fout<<'\n';
    }
    return 0;

}