Fişierul intrare/ieşire:lacusta.in, lacusta.outSursăOJI 2005, clasa a 10-a
AutorNistor Eugen MotAdăugată deFlorianFlorian Marcu Florian
Timp execuţie pe test0.1 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/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.inlacusta.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)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content