Se citesc doua numere naturale n si m, o matrice cu n linii si m coloane continand valori 0 (celula libera) sau 1 , coordonatele unei celule de start (si,sj), ale unei celule de final (fi,fj), si un numar natural k. Determinati, folosind metoda Backtracking, numarul de drumuri de lungime exact k (exact k pasi) de la start la final, deplasandu-va cu un pas in una din cele 4 directii intre celule libere (o celula poate fi vizitata de mai multe ori in acelasi drum).
- 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, k.
- Date de iesire
- Se afiseaza un singur numar: numarul de drumuri de lungime exact k de la start la final.
- Restrictii
- 1 <= n, m <= 6, 0 <= k <= 8
Exemple
Exemplul 1
Intrare
3 3 0 0 0 0 0 0 0 0 0 1 1 3 3 4
Iesire
6
Exemplul 2
Intrare
2 2 0 0 0 0 1 1 2 2 2
Iesire
2