Fișierul intrare/ieșire lacusta.in, lacusta.out Sursă OJI 2005 clasa a 10-a
Autor Nistor-Eugen Moț Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in lacusta.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii