# PBinfo #3258 – Alice_XI – Rezolvare C++

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

## Enunț

Cerinţa
Alice s-a pierdut din nou în labirint. Labirintul este de forma unui triunghi dreptunghic împărțit în camere organizate pe linii și coloane.  Pe prima linie este o singură cameră, pe a doua sunt două camere, etc. Pe ultima linie sunt n camere. Din fiecare cameră se poate merge în camerele situate pe linia următoare și pe aceeași coloană, sau pe coloane cu 1 mai mari sau mai mici decât coloana curentă, dar fără să se părăsească labirintul. Astfel din camera (i,j) se poate merge în camerele (i+1,j-1), (i+1,j) și (i+1,j+1), dacă acestea există. Alice se află în camera de pe prima linia și de pe prima coloana (1,1).

Ca să iasă din labirint, Alice trebuie să ajungă într-o cameră de pe ultima linie. Calculați și afișați numărul de trasee pe care poate Alice să iasă din labirint. 

Date de intrare
Fișierul de intrare alice_xi.in conține pe prima linie numărul n, reprezentând numărul de linii din labirint.

Date de ieşire
Fişierul de ieşire alice_xi.out va conţine pe prima linie numărul s, reprezentând numărul de trasee pe care poate Alice să iasă din labirint.

Restricţii şi precizări

1 ≤ n ≤ 35

Exemplu:
alice_xi.in

3
alice_xi.out

5
Explicație
Pe ultima linie sunt 3 camere. În prima se poate ajunge în 2 moduri, în cea de-a doua în 2 noduri, iar în a treia într-un singur mod. În total sunt 5 moduri în care se poate ajunge pe ultima linie.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream fin("alice_xi.in");
ofstream fout("alice_xi.out");
int main()
{
    long long A[101][101],c=0;
    int n;
    fin>>n;
    A[1][1]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(j==1) A[i][j]=A[i-1][j]+A[i-1][j+1];
            else if(j==i-1) A[i][j]=A[i-1][j-1]+A[i-1][j];
                 else if(j==i) A[i][j]=A[i-1][j-1];
                      else A[i][j]=A[i-1][j-1]+A[i-1][j]+A[i-1][j+1];
    for(int i=1;i<=n;i++)
        c=c+A[n][i];
    fout<<c;
    return 0;
}
```

## Resurse

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