3084 - Cub Dinamic: Difference between revisions
Pagină nouă: ==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... |
No edit summary |
||
Line 45: | Line 45: | ||
fără a trece prin camere blocate. | fără a trece prin camere blocate. | ||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python3"> | |||
MOD = 1234567 | MOD = 1234567 | ||
def numar_moduri(n, m, camere_blocate): | 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__": | 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> |
Revision as of 17:35, 11 January 2024
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"> 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>