| Fişierul intrare/ieşire: | labirint2.in, labirint2.out | Sursă | OJSEPI 2021, clasa a 10-a |
| Autor | Gheorghe Manolache, Stefan Dascalescu | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 64000 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | labirint2.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.
