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.

fără a trece prin camere blocate.

#include <bits/stdc++.h>

using namespace std;
#define mod 1234567
ifstream cin("cub_dinamic.in");
ofstream cout("cub_dinamic.out");

int n , m , x[201][201][201] , a , b , c;

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> a >> b >> c;
        x[a][b][c] = -1;
    }
    x[1][1][1] = 1;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            for(int k = 1 ; k <= n ; k++)
                if(x[i][j][k] != -1)
                {
                    if(x[i - 1][j][k] != -1)
                        x[i][j][k] += (x[i - 1][j][k])%mod;
                    if(x[i][j - 1][k] != -1)
                        x[i][j][k] += (x[i][j - 1][k])%mod;
                    if(x[i][j][k- 1] != -1)
                        x[i][j][k] += (x[i][j][k - 1])%mod;
                    x[i][j][k] %= mod;
                }
        }
    }
    cout << x[n][n][n];
}