Problema 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 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ță

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

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ă 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) < 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 puncte

• 1 ≤ N ≤ 50
• 1 ≤ M ≤ 50

Pentru alte 60 de puncte

• Fără alte restricții

Exemplu