Rezolvare PBinfo #937

Cerința

Hercule trebuie sa strabată un labirint cu capcane reprezentat de o matrice cu n linii și m coloane. Pentru fiecare celula a labirintului, se cunoaște timpul exprimat în minute după care celula respectivă devine capcană. După ce o celula devine capcana, Hercule piere dacă intră în acea celulă. Initial Hercule se află în celula de coordonate (1, 1) și trebuie să ajungă în celula de cordonate (n,m).

Sa se afișeze numarul total de drumuri pe care le poate urma Hercule prin labirint, astfel încât Hercule să nu piară.

Date de intrare

Fișierul de intrare hercule.in conține pe prima linie numerele n m, iar pe următoarele n linii câte m valori naturale.

Date de ieșire

Fișierul de ieșire hercule.out va conține pe prima linie numărul total de drumuri prin care Hercule poate ajunge în celula destinație.

Restricții și precizări

• 1 ≤ n , m ≤ 10
• Hercule nu poate intra de mai multe ori in aceeasi celula
• Hercule are nevoie de un minut,ca sa treacă dintr-o celula într-una vecină
• Hercule se deplasează pe direcțiile N-S și E-V.

Exemplu:

hercule.in

4 5
4 1 1 8 1 
6 3 4 5 1 
3 2 8 8 8 
1 3 4 2 9 

hercule.out

2

Explicație

Cele două trasee posibile ale lui Hercule sunt:

1 0 0 0 0 
2 3 4 5 0 
0 0 0 6 7 
0 0 0 0 8 

şi

1 0 0 0 0 
2 3 4 0 0 
0 0 5 6 7 
0 0 0 0 8