# PBinfo #3084 – cub_dinamic – Rezolvare C++

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

## Enunț

Cerința
Se dă un tablou tridimensional, de dimensiune \(n\) x \(n\) x \(n\), fiecare element reprezentând o camera. \(m\) dintre acestea sunt blocate și nu pot fi traversate. Dintr-o cameră având coordonatele \((i,j,k)\) te poți deplasa in camerele de coordonate \((i+1,j,k)\), \((i,j+1,k)\) și \((i,j,k+1)\).

Știind că pornești din camera cu coordonate \((1,1,1)\), se cere să se afișeze numărul de moduri modulo \(1234567\) de a ajunge in camera de coordonate \((n,n,n,)\).

Date de intrare
Fișierul de intrare cub_dinamic.in conține pe prima linie numerele n și m, iar pe următoarele m linii câte 3 numere  reprezentând coordonatele camerelor blocate.

Date de ieșire
Fișierul de ieșire cub_dinamic.out va conține pe prima linie numărul S, reprezentând numărul de moduri modulo \(1234567\) de a ajunge din camera \((1,1,1)\) în camera \((n,n,n)\).

Restricții și precizări

1 ≤ n ≤ 200
1 ≤ coordonatele camerelor ≤ n
0 ≤ m ≤ n*n*n
Dacă nu se poate ajunge in camera \((n,n,n)\) sau una dintre camerele \((1,1,1)\) sau \((n,n,n)\) este blocată, atunci se va afișa 0.

Exemplu:
cub_dinamic.in

3 1
2 2 2
cub_dinamic.out

54
Explicație
Există 54 de moduri de a ajunge din camera \((1,1,1)\) în camera \((n,n,n)\) fără a trece prin camere blocate.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define MOD 1234567
using namespace std;
ifstream fin ("cub_dinamic.in");
ofstream fout ("cub_dinamic.out");
bool M[205][205][205];
int  dp[205][205][205];
int main()
{
    int n, m, i, j, k, x, y, z;
    fin >> n >> m;
    for (i=1; i<=m; i++){
        fin >> x >> y >> z;
        M[x][y][z] = 1;
    }
    dp[1][1][1] = 1;
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            for (k=1; k<=n; k++){
                if ((i!=1 or j!=1 or k!=1) and M[i][j][k] == 0)
                dp[i][j][k] = dp[i-1][j][k] + dp[i][j-1][k] + dp[i][j][k-1];
                dp[i][j][k] %= MOD;
            }
    fout << dp[n][n][n] << "\n";
    return 0;
}
```

## Resurse

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