Labirint

Un labirint este descris ca fiind o matrice binară cu $N$ linii și $M$ coloane, cu semnificația că $0$ reprezintă o poziție liberă, iar $1$ reprezintă o poziție în care se află un zid. Un drum în labirint este un traseu în matrice care începe cu poziția $(1, 1)$ și ajunge în poziția $(N, M)$ prin deplasare doar pe poziții care au valoarea 0 și sunt vecine cu poziția curentă, pe una din cele patru direcții: sus, jos, stânga, dreapta. Lungimea unui drum este egală cu numărul de poziții vizitate.

Notăm cu $d_0$ lungimea drumului minim de la poziția $(1, 1)$ la poziția $(N, M)$. Fie $d(i, j)$ lungimea drumului minim de la poziția $(1, 1)$ la poziția $(N, M)$, dacă poziției $(i, j)$ i se atribuie valoarea $0$. Observăm că dacă poziția $(i, j)$ conține inițial un $0$, atunci $d_0 = d(i, j)$.

Cerință

Pentru fiecare poziție $(i, j)$, să se verifice dacă $d(i, j) < d_0$.

Date de intrare

Pe prima linie a fișierului labirint.in se află două numere naturale $N$ și $M$, dimensiunile matricei binare ce descrie labirintul, apoi pe următoarele $N$ linii se vor afla câte $M$ valori binare, ce reprezint˘a elementele matricei care descrie labirintul, neseparate prin spații.

Date de ieșire

în fișierul labirint.out se vor scrie $N$ linii, iar pe fiecare linie se vor scrie $M$ cifre, neseparate prin spații. Cifra a $j$-a de pe linia a $i$-a este $1$ dacă și numai dacă $d(i, j) < d_0$, altfel este $0$.

Restricții și precizări

• $1 \leq N, M \leq 1 \ 000$;
• Pe pozițiile $(1, 1)$ și $(N, M)$ se vor afla valori $0$.
• Se garantează că există un drum în matricea inițială între pozițiile $(1, 1)$ și $(N, M)$.

Exemplu

labirint.in

5 6
010001
000101
011001
010010
001000

labirint.out

010000
000100
001001
010010
001000

Explicație

Sunt $7$ poziții cu valoarea $1$ în labirint care dacă se înlocuiesc cu $0$ determină obținerea unui drum de lungime mai mică decât $d_0 = 14$.

De exemplu, dacă am înlocui valoarea din $(1, 2)$ cu $0$, am obține un drum de lungime $d(1, 2) = 12$.