Fişierul intrare/ieşire:lacusta.in, lacusta.outSursăOJI 2005 clasa a 10-a
AutorNistor-Eugen MotAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Lăcusta (clasa a 10-a)

Se consideră o matrice dreptunghiulară cu m linii şi n coloane, cu valori naturale. Traversăm matricea pornind de la colţul stânga-sus la colţul dreapta-jos. O traversare constă din mai multe deplasări. La fiecare deplasare se execută un salt pe orizontală şi un pas pe verticală. Un salt înseamnă că putem trece de la o celulă la oricare alta aflată pe aceeaşi linie, iar un pas înseamnă că putem trece de la o celulă la celula aflată imediat sub ea. Excepţie face ultima deplasare (cea în care ne aflăm pe ultima linie), când vom face doar un salt pentru a ajunge în colţul dreapta-jos, dar nu vom mai face şi pasul corespunzător. Astfel traversarea va consta din vizitarea a 2m celule.

Cerinţă

Scrieţi un program care să determine suma minimă care se poate obţine pentru o astfel de traversare.

Date de intrare

Fişierul de intrare lacusta.in conţine pe prima linie două numere naturale separate printr-un spaţiu m n, reprezentând numărul de linii şi respectiv numărul de coloane ale matricei. Pe următoarele m linii este descrisă matricea, câte n numere pe fiecare linie, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire lacusta.out va conţine o singură linie pe care va fi scrisă suma minimă găsită.

Restricţii

  • 1 ≤ m, n ≤ 100
  • Valorile elementelor matricei sunt numere întregi din intervalul [1, 255]

Exemplu

lacusta.inlacusta.outExplicaţii
4 5
3 4 5 7 9
6 6 3 4 4
6 3 3 9 6
6 5 3 8 2
28
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