# PBinfo #4011 – Moș Crăciun XI – Rezolvare C++

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

## Enunț

Cerința
Pentru a-i duce cadoul dorit lui Dorel, Moș Crăciun trebuie să străbată un labirint cu capcane reprezentat de o matrice cu n linii și n coloane. Fiecare celula a labirintului este marcată cu valoarea 1 dacă este capcană sau cu 0 dacă este poziție liberă. Inițial, Moș Crăciun se află în celula de coordonate (1, 1),  iar Dorel în celula de coordonate (n,n).

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

Moș Crăciun dorește să știe numărul total de drumuri pe care le poate urma prin labirint până la poziția în care se află Dorel, astfel încât să nu treacă prin capcane și să nu treacă de mai multe ori prin aceeași pozitie. De asemenea, Moș Crăciun vrea să îl facă pe Dorel să îl aștepte cât mai mult și ar vrea să știe lungimea celui mai lung drum. Dacă îl ajutați să calculeze aceste numere, atunci Moș Crăciun promite că va trece și pe la voi.

Date de intrare
Se citește de la tastatură numărul n, iar de pe următoarele n linii câte n valori de 0 sau 1 cu semnificația din enunț, separate prin câte un spațiu.

Date de ieșire
Se va afișa pe ecran numărul de moduri în care poate ajunge Moș Crăciun din poziția inițială în poziția unde îl așteaptă Dorel. Pe linia următoare se va scrie numărul de celule din care este format cel mai lung drum.
Dacă Moș Crăciun nu poate ajunge la Dorel, atunci se va afișa mesajul Dorel :((

Restricții și precizări

1 ≤ n  ≤ 10
pozițiile (1,1) și (n,n) nu sunt capcane

Exemplu:
Intrare

5
0 1 1 0 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0
Ieșire

4
9
Explicație
Cele 4 drumuri posibile sunt:


1 1 1 0 0
1 2 0 0 0
0 1 3 0 0
0 0 0 4 1
0 0 1 0 5 

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

1 1 1 0 0
1 2 0 0 0
3 1 5 0 0
0 4 0 6 1
0 0 1 0 7
şi


1 1 1 0 0
1 2 0 6 0
3 1 5 0 7
0 4 0 8 1
0 0 1 0 9
Ultimul este traseul format din cele mai multe celule, adică 9.

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
int di[]={-1,-1,1,1};
int dj[]={-1,1,1,-1};
int n,A[12][12],c,lmax;
int inside(int i, int j)
{
    return i>=1 && i<=n && j>=1 && j<=n;
}
void back(int i, int j, int k)
{
    A[i][j]=k;
    if(i==n && j==n) { c++; if(k>lmax) lmax=k; }
    else
        for(int d=0;d<=3;d++)
        {
            int iv=i+di[d], jv=j+dj[d];
            if(inside(iv,jv) && A[iv][jv]==0) back(iv,jv,k+1);
        }
    A[i][j]=0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>A[i][j];
    back(1,1,1);
    if(c==0) cout<<"Dorel :((";
    else cout<<c<<endl<<lmax;
    return 0;
}
```

## Resurse

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