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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema cub_dinamic:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3084 cub_dinamic

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3084 cub_dinamic de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3084 cub_dinamic