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). Generati, folosind metoda Backtracking, toate drumurile simple (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 (sus, jos, stanga, dreapta) 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 toate drumurile gasite, cate unul pe linie, ca succesiune de coordonate 'linie,coloana' separate prin spatiu, in ordinea in care sunt generate incercand la fiecare pas directiile in ordinea: sus, jos, stanga, dreapta.
- Restrictii
- 1 <= n, m <= 4
Exemple
Exemplul 1
Intrare
2 2 0 0 0 0 1 1 2 2
Iesire
1,1 2,1 2,2 1,1 1,2 2,2
Exemplul 2
Intrare
3 3 0 0 0 0 0 0 0 0 0 1 1 3 3
Iesire
1,1 2,1 3,1 3,2 2,2 1,2 1,3 2,3 3,3 1,1 2,1 3,1 3,2 2,2 2,3 3,3 1,1 2,1 3,1 3,2 3,3 1,1 2,1 2,2 1,2 1,3 2,3 3,3 1,1 2,1 2,2 3,2 3,3 1,1 2,1 2,2 2,3 3,3 1,1 1,2 2,2 3,2 3,3 1,1 1,2 2,2 2,1 3,1 3,2 3,3 1,1 1,2 2,2 2,3 3,3 1,1 1,2 1,3 2,3 3,3 1,1 1,2 1,3 2,3 2,2 3,2 3,3 1,1 1,2 1,3 2,3 2,2 2,1 3,1 3,2 3,3