# PBinfo #4012 – Matrix XI – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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ă.

## Cod sursă C++

```cpp
#include<iostream>
using namespace std;
const int di[]={-1,1,0,0};
const int dj[]={0,0,-1,1};
int A[12][12],c,n,m,x,y,p;
int inside(int i,int j)
{
   return i>=1 && i<=n && j>=1 && j<=m;
}
void back(int i, int j, int k)
{
    A[i][j]--;
    if(k==p) c++;
    else for(int d=0;d<4;d++)
    {
        int iv=i+di[d];
	    int jv=j+dj[d];
	    if(inside(iv,jv) && A[iv][jv]>0)
		   back(iv,jv,k+1);
    }
    A[i][j]++;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++)
        {
            cin>>A[i][j];
			p=p+A[i][j];
		}
   cin>>x>>y;
   back(x,y,1);
   if(c==0) cout<<"Mr. Anderson wins!";
   else cout<<c;
   return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4012)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4012/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4012/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)