Se citesc doua numere naturale n si m, apoi o matrice cu n linii si m coloane continand valori 0 (celula libera) sau 1 (celula blocata). Determinati, folosind metoda Backtracking, numarul de moduri in care celulele libere pot fi acoperite complet cu piese domino de dimensiune 1x2 (orizontale sau verticale), fara suprapuneri si fara a acoperi celule blocate.
- 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 acoperiri complete posibile. Daca numarul de celule libere este impar, raspunsul este 0.
- Restrictii
- 1 <= n, m <= 5
Exemple
Exemplul 1
Intrare
2 2 0 0 0 0
Iesire
2
Exemplul 2
Intrare
2 3 0 0 0 0 0 0
Iesire
3