| Fişierul intrare/ieşire: | lacusta.in, lacusta.out | Sursă | OJI 2005, clasa a 10-a |
| Autor | Nistor Eugen Mot | Adăugată de |  Florian Marcu •Florian |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Lacusta
Se considera o matrice dreptunghiulara cu m linii si n coloane, cu valori naturale. Traversam matricea pornind de la coltul stanga-sus la coltul dreapta-jos. O traversare consta in mai multe deplasari. La fiecare deplasare se executa un salt pe orizontala si un pas pe verticala. Un salt inseamna ca putem trece de la o celula la oricare alta aflata pe aceeasi linie, iar un pas inseamna ca putem trece de la o celula la celula aflata imediat sub ea. Exceptie face ultima deplasare (cea in care ne aflam pe ultima linie), cand vom face doar un salt pentru a ajunge in coltul dreapta-jos, dar nu vom mai face si pasul corespunzator. Astfel traversarea va consta din vizitarea a 2m celule.
Cerinta
Scrieti un program care sa determine suma minima care se poate obtine pentru o astfel de traversare.
Date de intrare
Fisierul de intrare lacusta.in contine pe prima linie doua numere naturale separate printr-un spatiu m n, reprezentand numarul de linii si, respectiv, numarul de coloane ale matricei. Pe urmatoarele m linii este descrisa matricea, cate n numere pe fiecare linie, separate prin cate un spatiu.
Date de iesire
Fisierul de iesire lacusta.out va contine o singura linie pe care va fi scrisa suma minima gasita.
Restrictii
- 1 < n, m ≤ 250
- Valorile elementelor matricei sunt numere intregi din intervalul [1, 255].
Exemplu
| lacusta.in | lacusta.out |
|---|---|
| 4 5 3 4 5 7 9 6 6 3 4 4 6 3 3 9 6 6 5 3 8 2 | 28 |
Explicatie:
Drumul este:
(1,1)->(1,3)->
(2,3)->(2,2)->
(3,2)->(3,3)->
(4,3)->(4,5)
