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, lungimea celui mai lung drum SIMPLU (fara a trece de doua ori prin aceeasi celula) de la start la final, deplasandu-va cu un pas in una din cele 4 directii intre celule libere.
- 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 (numarul de pasi) celui mai lung drum simplu de la start la final. Daca nu exista niciun drum, se afiseaza -1.
- Restrictii
- 1 <= n, m <= 4
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
8