Se da un labirint de R linii si C coloane ('0' = celula libera, '1' = perete), un punct de start si un punct de sosire. Determinati numarul minim de pasi (miscari sus/jos/stanga/dreapta) pentru a ajunge de la start la sosire, trecand doar prin celule libere.
- Date de intrare
- Pe prima linie se citesc R si C. Urmeaza R linii, fiecare cu C caractere ('0' sau '1'), fara spatii. Pe ultima linie se citesc r1, c1, r2, c2 (linia si coloana celulei de start, respectiv a celei de sosire, 1-indexate; ambele celule sunt garantat libere).
- Date de iesire
- Se afiseaza numarul minim de pasi, sau -1 daca sosirea nu este accesibila din start.
- Restrictii
- 1 <= R, C <= 500
Exemple
Exemplul 1
Intrare
3 3 000 010 000 1 1 3 3
Iesire
4
Exemplul 2
Intrare
3 3 000 111 000 1 1 3 3
Iesire
-1