Fişierul intrare/ieşire:labirint2.in, labirint2.outSursăOJSEPI 2021, clasa a 10-a
AutorGheorghe Manolache, Stefan DascalescuAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test0.4 secLimită de memorie64000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Labirint2

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, 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.

Exemplu

labirint2.inlabirint2.out
5 6
010001
000101
011001
010010
001000
010000
000100
001001
010010
001000

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?