Editing 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 &les; m,n &les; 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
 4 5
 4 1 1 8 1 
 6 3 4 5 1 
 3 2 8 8 8 
 1 3 4 2 9 
; herculeout.txt
 Datele de intrare corespund restrictiilor impuse
 2
<br>
== Exemplu 2 ==
; herculein.txt
 4 11
 4 1 1 8 1
 6 3 4 5 1
 3 2 8 8 8
 1 3 4 2 9
; herculeout.txt
 Datele de intrare nu corespund restrictiilor impuse
<br>
== 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:
 1 0 0 0 0 
 2 3 4 5 0 
 0 0 0 6 7 
 0 0 0 0 8
; si
 1 0 0 0 0 
 2 3 4 0 0 
 0 0 5 6 7 
 0 0 0 0 8