Diferențe pentru problema/traseu între reviziile #7 si #4

== include(page="template/taskheader" task_id="traseu") ==

Sătul de atâtea olimpiade și concursuri, Algorel a plecat la munte, să se relaxeze. Odată ajuns acolo s-a hotărât să urmeze un traseu cu peisaje cât mai frumoase. El are la dispoziție o hartă codificată sub forma unei matrice cu $M$ linii și $N$ coloane, ale cărei elemente sunt numere naturale nenule reprezentând gradul de frumusețe corespunzător fiecărei zone (element al matricei). Algorel trebuie să plece din colțul stânga sus al matricei (poziția $(1,1)$) și să ajungă în colțul dreapta jos (poziția $(M,N)$), având voie să se deplaseze doar spre dreapta și în jos (de pe poziția curentă $(i,j)$ se poate deplasa fie pe poziția $(i+1,j)$, fie pe poziția $(i,j+1)$). Definim gradul de frumusețe al unui traseu ca fiind suma gradelor de frumusețe ale elementelor matricei care-l compun. Se cere găsirea gradului maxim de frumusețe pe care îl poate avea un traseu care respectă restricțiile de mai sus.

Sătul de atâtea olimpiade și concursuri, Algorel a plecat la munte, să se relaxeze. Odată ajuns acolo s-a hotărât să urmeze un traseu cu peisaje cât mai frumoase. El are la dispoziție o hartă codificată sub forma unei matrice cu $M$ linii și $N$ coloane, ale cărei elemente sunt numere naturale nenule reprezentând gradul de frumusețe corespunzător fiecărei zone (element al matricei). Algorel trebuie să plece din colțul stânga sus al matricei (poziția $(1,1)$) și să ajungă în colțul dreapta jos (poziția $(M,N)$) având voie să se deplaseze doar spre dreapta și în jos (de pe poziția curentă $(i,j)$ se poate deplasa fie pe poziția $(i+1,j)$, fie pe poziția $(i,j+1)$). Se cere găsirea sumei maxime a gradelor de frumusețe pe care o poate avea un traseu care respectă restricțiile de mai sus.

h2. Date de intrare

table(example).
|_. traseu.in |_. traseu.out |
| 2 3

1 10 20
11 2 3

  1 10 20
  11 2 3

| 34
|
h3. Explicație

Traseul optim trece prin zonele (1,1), (1,2), (1,3), (2,3).

...

== include(page="template/taskfooter" task_id="traseu") ==