Vizualizare sursă pentru „3084 - Cub Dinamic”

==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.
==Rezolvare==
<syntaxhighlight lang="python3" line="1">
MOD = 1234567

def numar_moduri(n, m, camere_blocate):

   dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
   # Inițializăm matricea cu 0-uri
   for i in range(n + 1):
       for j in range(n + 1):
           for k in range(n + 1):
               dp[i][j][k] = 0
   # Marcam camerele blocate cu -1
   for i, j, k in camere_blocate:
       dp[i][j][k] = -1
   # Dacă camera finală este blocată sau camera de plecare este blocată, returnăm 0
   if dp[1][1][1] == -1 or dp[n][n][n] == -1:
       return 0
   dp[1][1][1] = 1
   for i in range(1, n + 1):
       for j in range(1, n + 1):
           for k in range(1, n + 1):
               # Dacă camera este blocată, continuăm
               if dp[i][j][k] == -1:
                   continue
               # Actualizăm modul în care putem ajunge în camerele adiacente
               if i + 1 <= n and dp[i + 1][j][k] != -1:
                   dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MOD
               if j + 1 <= n and dp[i][j + 1][k] != -1:
                   dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i][j][k]) % MOD
               if k + 1 <= n and dp[i][j][k + 1] != -1:
                   dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i][j][k]) % MOD
   return dp[n][n][n]

if __name__ == "__main__":

   with open("cub_dinamic.in", "r") as f:
       n, m = map(int, f.readline().split())
       camere_blocate = [tuple(map(int, f.readline().split())) for _ in range(m)]
   rezultat = numar_moduri(n, m, camere_blocate)
   with open("cub_dinamic.out", "w") as g:
       g.write(str(rezultat) + "\n")
</syntaxhighlight>