Rezolvare PBinfo #4012

Cerința

Pentru a evada din Matrix, Neo trebuie să străbată un labirint reprezentat de o matrice cu n linii și m coloane. Fiecare celulă a labirintului este marcată cu o cifră în baza 10 cu semnificația că Neo trebuie să treacă prin acea poziție de atâtea ori cât este valoarea cifrei din acea poziție. Practic, Neo poate merge doar pe poziții care au valori nenule. Inițial, Neo se află în celula de coordonate (x, y), cunoscută.

Neo se poate deplasa doar pe valori vecine pe linie și pe coloană. Dacă se află în poziția (i,j), atunci el poate merge în pozițiile (i-1,j), (i+1,j), (i,j+1) și (i,j-1).

Neo vrea să știe numărul total de moduri în care poate parcurge labirintul. Dacă îl ajutați să calculeze acest număr, atunci Neo va insista pe lângă Moș Crăciun să vă aducă bomboane roșii și albastre.

Date de intrare

Se citește de la tastatură numerele n și m, iar de pe următoarele n linii câte m valori cu semnificația din enunț, separate prin câte un spațiu. Apoi se citește poziția (x,y).

Date de ieșire

Se va afișa pe ecran numărul de moduri în care Neo poate parcurge labirintul, pornind din poziția inițială și trecând prin fiecare poziție de atâtea ori cât este valoarea cifrei din acea poziție
Dacă Neo nu poate parcurge labirintul, atunci se va afișa mesajul Mr. Anderson wins!

Restricții și precizări

• 1 ≤ n,m ≤ 7
• elementele matricii sunt cuprinse între 0 și 9
• pozițiia (x,y) are valoare nenulă

Exemplu:

Intrare

6 7
0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 1 2 0 2 1 0
0 0 1 0 1 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 2

Ieșire

2

Explicație

Cele două drumuri posibile sunt:

(3,2) (3,3) (4,3) (3,3) (2,3) (2,4) (2,5) (3,5) (4,5) (3,5) (3,6)
(3,2) (3,3) (4,3) (3,3) (2,3) (2,4) (2,5) (3,5) (3,6) (3,5) (4,5)
Prin pozițiile (3,3) și (3,5) se trece de câte două ori, în rest câte o dată.