Se citesc doua numere naturale n si m, o matrice cu n linii si m coloane continand valori 0 (celula libera) sau 1 , si coordonatele unei celule de start (si,sj) si ale unei celule de final (fi,fj). Determinati, folosind metoda Backtracking (generand drumurile posibile si retinand cea mai mica lungime intalnita, fara a folosi parcurgerea in latime BFS), lungimea minima (numarul minim de pasi) a unui drum de la start la final, deplasandu-va cu un pas in una din cele 4 directii intre celule libere, fara a trece de doua ori prin aceeasi celula.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza n linii, fiecare cu m valori (0 sau 1). Pe ultima linie se citesc si, sj, fi, fj.
- Date de iesire
- Se afiseaza un singur numar: lungimea minima a unui drum de la start la final. Daca nu exista niciun drum, se afiseaza -1.
- Restrictii
- 1 <= n, m <= 6
Exemple
Exemplul 1
Intrare
2 2 0 0 0 0 1 1 2 2
Iesire
2
Exemplul 2
Intrare
3 3 0 0 0 0 0 0 0 0 0 1 1 3 3
Iesire
4