Enunț oficial — sursă externă

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, apoi pe următoarele $N$ linii câte $M$ valori binare (elementele matricei), neseparate prin spații.

Date de ieșire

În fișierul labirint.out se scriu $N$ linii, fiecare cu $M$ cifre neseparate. Cifra a $j$-a de pe linia a $i$-a este $1$ dacă și numai dacă $d(i, j) < d_0$, altfel $0$.

Restricții și precizări

• $1 \leq N, M \leq 1\,000$;
• pe pozițiile $(1, 1)$ și $(N, M)$ se află valori $0$;
• se garantează că există un drum între $(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$ care, înlocuite cu $0$, dau un drum mai scurt decât $d_0 = 14$. De exemplu, înlocuind valoarea din $(1, 2)$ cu $0$ se obține un drum de lungime $d(1, 2) = 12$.

Intuiție: ce ne întreabă, de fapt, problema

Ai un labirint și un drum minim de la colțul stânga-sus la colțul dreapta-jos, de lungime $d_0$. Întrebarea nu e „care e drumul minim?” (acela e fix, $d_0$), ci ceva mai subtil: pentru fiecare celulă din matrice, dacă am sparge acolo un zid (am pune $0$ în loc de $1$), s-ar scurta drumul minim?

Două observații ne simplifică viața înainte să scriem o linie de cod:

• O celulă care e deja liberă ($0$) nu poate ajuta. Drumul minim trece deja peste celulele libere disponibile; a „deschide” una deja deschisă nu schimbă nimic, deci $d(i,j) = d_0$ și răspunsul e mereu $0$. Doar zidurile contează.
• Un zid ajută doar dacă el oferă o scurtătură — o legătură directă între două porțiuni ale labirintului care altfel sunt mai depărtate. Practic, ne interesează cât de aproape de start, respectiv de final, sunt vecinii liberi ai acelui zid.

Ideea cheie: două BFS-uri în loc de un milion

Soluția naivă ar reface drumul minim de la zero pentru fiecare celulă: pune $(i,j) = 0$, rulează un BFS, compară cu $d_0$. Asta înseamnă $N \cdot M$ rulări de BFS, fiecare $O(N M)$, deci $O((N M)^2) \approx 10^{12}$ operații pentru $N = M = 1000$. Imposibil în timp.