== include(page="template/taskheader" task_id="labirint2") ==

Poveste şi cerinţă...

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)$.
 
 
h2. Cerinţă
 
Pentru fiecare poziţie $(i, j)$, să se verifice dacă $d(i, j) < d0$.

h2. Date de intrare

Fişierul de intrare $labirint2.in$ ...

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ă elementele matricei care descrie labirintul, neseparate prin spaţii.

h2. Date de ieşire

În fişierul de ieşire $labirint2.out$ ...

Î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) < d0$, altfel este $0$.
 
h2. Restricţii şi precizări

h2. Restricţii

* $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, M ≤ 50, d0 = N + M - 1$.
* Pentru alte 30 de puncte $1 ≤ N, M ≤ 50$.
* *Atenţie!* Este posibil ca punctajul să difere faţă de cel luat în concurs.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. labirint2.in |_. labirint2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 6
010001
000101
011001
010010
001000
| 010000
000100
001001
010010
001000

|

h3. Explicaţie

h3. Explicaţii
 
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$.

== include(page="template/taskfooter" task_id="labirint2") ==