Se citesc doua numere naturale n si m, apoi o matrice de costuri cu n linii si m coloane. Determinati, folosind metoda Backtracking, costul minim al unui drum de la celula (1,1) la celula (n,m), stiind ca la fiecare pas ne putem deplasa fie la dreapta, fie in jos, iar costul unui drum este suma costurilor tuturor celulelor vizitate (inclusiv (1,1) si (n,m)).
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza n linii, fiecare cu m valori intregi reprezentand costurile celulelor.
- Date de iesire
- Se afiseaza un singur numar: costul minim al unui drum de la (1,1) la (n,m).
- Restrictii
- 1 <= n, m <= 12, -1000 <= cost <= 1000
Exemple
Exemplul 1
Intrare
2 2 1 2 3 4
Iesire
7
Exemplul 2
Intrare
3 3 1 3 1 1 5 1 4 2 1
Iesire
7