0973 - Cuvinte 1

Cerinţa

Hercule trebuie sa strabată un labirint cu capcane reprezentat de o matrice cu n linii și m coloane. Pentru fiecare celula a labirintului, se cunoaște timpul exprimat în minute după care celula respectivă devine capcană. După ce o celula devine capcana, Hercule piere dacă intră în acea celulă. Initial Hercule se află în celula de coordonate (1, 1) și trebuie să ajungă în celula de cordonate (n,m).

Sa se afișeze numarul total de drumuri pe care le poate urma Hercule prin labirint, astfel încât Hercule să nu piară.

Date de intrare

Fișierul de intrare herculein.txt conține pe prima linie numerele n m, iar pe următoarele n linii câte m valori naturale.

Date de ieșire

Fișierul de ieșire herculeout.txt va conține pe prima linie numărul total de drumuri prin care Hercule poate ajunge în celula destinație.

Restricţii şi precizări

1 ⩽ m,n ⩽ 10
Hercule nu poate intra de mai multe ori in aceeasi celula
Hercule are nevoie de un minut,ca sa treacă dintr-o celula într-una vecină
Hercule se deplasează pe direcțiile N-S și E-V.

Exemplu

herculein.txt

herculeout.txt

Datele de intrare corespund restrictiilor impuse
2

Exemplu 2

herculein.txt

herculeout.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line> def numar_drumuri(matrice, n, m):

   dp = [[0 for _ in range(m)] for _ in range(n)]
   dp[0][0] = 1

   for i in range(n):
       for j in range(m):
           if i > 0 and matrice[i][j] > i + j:
               dp[i][j] += dp[i-1][j]
           if j > 0 and matrice[i][j] > i + j:
               dp[i][j] += dp[i][j-1]

   return dp[n-1][m-1]

def main():

   with open('herculein.txt', 'r') as fin:
       n, m = map(int, fin.readline().split())
       matrice = [list(map(int, linie.split())) for linie in fin]

   with open('herculeout.txt', 'w') as fout:
       if not (1 <= n <= 10 and 1 <= m <= 10):
           fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
           return
       fout.write("Datele de intrare corespund restrictiilor impuse\n")

       fout.write(str(numar_drumuri(matrice, n, m)) + '\n')

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicatie

Cele două trasee posibile ale lui Hercule sunt

si