problema/traseu4

traseu4

*I do not know what is this*

== include(page="template/taskheader" task_id="traseu4") ==
 
O suprafaţă de teren de formă dreptunghiulară este divizată în $N$ fâşii orizontale şi $M$ fâşii verticale, de lăţimi egale. Se formează astfel $N x M$ zone de formă pătrată, cu latura egală cu o unitate. Astfel, suprafaţa este reprezentată sub forma unui tablou bidimensional cu $N$ linii şi $M$ coloane, în care pentru fiecare zonă este memorat un număr ce reprezintă altitudinea zonei respective. Interesant este că în tablou apar toate valorile $1, 2, …, N*M. Suprafaţa este destinată turismului. Deoarece spre laturile de Est şi Sud ale suprafeţei există peisaje de o frumuseţe uimitoare, se doreşte găsirea unor trasee turistice în care deplasarea să se realizeze cu paşi de lungime unitară mergând doar spre Est şi spre Sud. O comisie, care trebuie să rezolve această problemă, a stabilit că un traseu este atractiv dacă şi numai dacă ultima poziţie a traseului are altitudinea mai mare decât prima poziţie a traseului. Un traseu poate începe, respectiv se poate încheia, în oricare dintre zonele terenului, cu respectarea condiţiilor anterioare.
Se cere să se determine numărul maxim $Z$ de zone pe care le poate avea un traseu atractiv.
 
h2. Date de intrare
 
În fişierul de intrare $traseu4.in$ se află scrise pe prima linie numerele $N$ şi $M$, cu semnificaţia din enunţ. Pe fiecare dintre următoarele $N$ linii se află scrise câte $M$ numere naturale, reprezentând, elementele tabloului bidimensional precizat în enunţ. Numerele aflate pe aceeaşi linie a fişierului sunt separate prin câte un spaţiu.
 
h2. Date de ieşire
 
În fişierul de ieşire $traseu4.out$ se va scrie numărul $Z$, cu semnificaţia din enunţ. Dacă nu există niciun traseu atractiv, atunci se va scrie $0$.
 
h2. Restricţii
 
* $1 ≤ N ≤ 500$
* $1 ≤ M ≤ 500$
* Pentru teste in valoare de $40$ de puncte, $N ≤ 50$ şi $M ≤ 50$
* $10$ puncte sunt din oficiu: corespund unor teste egale cu primul exemplu.
 
h2. Exemplu
 
table(example).
|_. traseu4.in
|_. traseu4.out
|_. Explicaţii
|
| 3 4
12 11 10 6
7 5 4 3
9 2 8 1
|4
| Traseele atractive de lungime 2 sunt: 7-9, 4-8, 2-8
Traseele atractive de lungime 3 sunt: 5-2-8, 5-4-8
Traseele atractive de lungime 4 (maximă) sunt:
7-5-4-8, 7-5-2-8, 7-9-2-8.
|
| 3 3
5 8 7
9 6 4
3 1 2
| 3
| Traseele atractive de lungime 2 sunt: 5-8, 5-9, 1-2
Traseele atractive de lungime 3 (maximă) sunt: 5-9-6,5-8-6,5-8-7
|
 
== include(page="template/taskfooter" task_id="traseu4") ==
 

public

task: traseu4