Labirint5

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

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

char a[1001][1001];
int n, m, d1[1001][1001], d2[1001][1001], di[] = {-1, 0, 1, 0}, dj[] = {0, 1, 0, -1};
/// d1[i][j] - lungimea minima a unui drum ce pleaca din pozitia (1, 1) si ajunge in pozitia (i, j)
/// d2[i][j] - lungimea minima a unui drum ce pleaca din pozitia (N, M) si ajunge in pozitia (i, j)

struct pozitie {
    int i, j;
} q[1001 * 1001];

void Lee1() {
    int st = 1, dr = 0;
    pozitie aux;
    aux.i = 1, aux.j = 1;
    ++dr;
    q[dr] = aux;
    d1[1][1] = 1;
    while (st <= dr) {
        int i = q[st].i, j = q[st].j;
        ++st;
        for (int k = 0; k < 4; ++k) {
            int iv = i + di[k], jv = j + dj[k];
            if (1 <= iv && iv <= n && 1 <= jv && jv <= m) {
                if (d1[iv][jv] == INF) {
                    d1[iv][jv] = d1[i][j] + 1;
                    if (a[iv][jv] == '0') {
                        aux.i = iv, aux.j = jv;
                        q[++dr] = aux;
                    }
                }
            }
        }
    }
}

void Lee2() {
    int st = 1, dr = 0;
    pozitie aux;
    aux.i = n, aux.j = m;
    ++dr;
    q[dr] = aux;
    d2[n][m] = 1;
    while (st <= dr) {
        int i = q[st].i, j = q[st].j;
        ++st;
        for (int k = 0; k < 4; ++k) {
            int iv = i + di[k], jv = j + dj[k];
            if (1 <= iv && iv <= n && 1 <= jv && jv <= m) {
                if (d2[iv][jv] == INF) {
                    d2[iv][jv] = d2[i][j] + 1;
                    if (a[iv][jv] == '0') {
                        aux.i = iv, aux.j = jv;
                        q[++dr] = aux;
                    }
                }
            }
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            fin >> a[i][j];
            d1[i][j] = d2[i][j] = INF;
        }
    }
    Lee1();
    Lee2();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i][j] == '1') {
                if (d1[i][j] + d2[i][j] - 1 < d1[n][m]) {
                    fout << '1';
                } else {
                    fout << '0';
                }
            } else {
                fout << '0';
            }
        }
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}