Rezolvare PBinfo #3717

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 d0 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 d0 = d(i, j).

Cerința

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

Date de intrare

Pe prima linie a fișierului de intrare 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ă elementele matricei care descrie labirintul, neseparate prin spații.

Date de ieșire

În fișierul de ieșire 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) < d0, altfel este 0.

Restricții și precizări

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 1000
• 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).
• Pentru 10 puncte, 1 ≤ N ≤ 50, 1 ≤ M ≤ 50, d0 = N + M - 1.
• Pentru alte 30 de puncte, 1 ≤ N ≤ 50, 1 ≤ M ≤ 50
• Pentru alte 60 de puncte, fără alte restricții

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 d0 = 14. De exemplu, dacă am înlocui valoarea din (1, 2) cu 0, am obține un drum de lungime d(1, 2) = 12.