Candale Silviu (silviu) Cerința
Se consideră harta unei suprafețe deșertice, dată sub forma unei matrice cu n linii și m coloane, formată din n*m zone. Fiecare zonă poate fi accesibilă sau inaccesibilă. Dintr-o zonă accesibilă se poate trece în altă zonă accesibilă învecinată cu prima pe linie sau pe coloană.
Un călător dorește să traverseze deșertul de la nord (prima linie) la sud (ultima linie). Pentru aceasta el poate sa aleagă oricare zonă accesibilă de pe prima line și dorește să ajungă pe ultima linie cu număr minim de pași.
Date de intrare
Fișierul de intrare traversare.in conține pe prima linie numerele n m. Următoarele n linii conțin câte m valori 0 sau 1, separate prin câte un spațiu. Valoarea 0 reprezintă o zonă accesibilă, iar valoarea 1 reprezintă o zonă inaccesibilă.
Date de ieșire
Fișierul de ieșire traversare.out va conține pe prima linie numărul C, reprezentând numărul minim de pași necesari pentru traversare.
Restricții și precizări
1 ≤ n, m ≤ 1000- în traversarea deșertului un pas este trecerea dintr-o zonă accesibilă în altă zonă accesibilă învecinată cu prima
- la determinarea numărului de pași se numără și primul pas (intrarea în matrice)
- pentru toate datele de test este posibilă traversarea deșertului
Exemplu:
traversare.in
6 9 1 1 0 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0
traversare.out
8
Explicație
O traversare cu 8 pași a deșertului este următoarea:
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |