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

Din pacate nu am reusit sa identificam autorul acestei probleme. Intra aici pentru a afla cum poti sa ne ajuti

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 din 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 2 m 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

Cum se trimit solutii?