Se citesc doua numere naturale n si m, apoi o matrice cu n linii si m coloane, continand valori 0 (celula libera) sau 1 . Determinati, folosind metoda Backtracking, numarul de drumuri de la celula (1,1) la celula (n,m), stiind ca la fiecare pas ne putem deplasa fie la dreapta, fie in jos, fara a trece prin celule obstacol.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza n linii, fiecare cu m valori (0 sau 1).
- Date de iesire
- Se afiseaza un singur numar: numarul de drumuri de la (1,1) la (n,m) care nu trec prin obstacole. Daca (1,1) sau (n,m) este obstacol, se afiseaza 0.
- Restrictii
- 1 <= n, m <= 12
Exemple
Exemplul 1
Intrare
2 2 0 0 0 0
Iesire
2
Exemplul 2
Intrare
3 3 0 0 0 0 1 0 0 0 0
Iesire
2