Rezolvare PBinfo #4000

Cerința

Harta unui munte este reprezentată printr-o matrice cu n linii și m coloane în care fiecare element reprezintă înălțimea zonei respective. Un alpinist pleacă de la coordonatele (1,1) și dorește să ajungă la coordonatele (n,m). Deplasarea se face pe aceeași linie sau coloană; alpinistul poate să treacă din zona curentă în zona învecinată numai dacă înălțimea zonei curente este mai mică sau egală cu cea a zonei învecinate.

Determinați lungimea maximă a unui traseu al alpinistului.

Date de intrare

Programul citește de la tastatură numerele n m, apoi n*m numere naturale, reprezentând harta muntelui.

Date de ieșire

Programul va afișa pe ecran numărul L, reprezentând lungimea maximă a unui traseu al alpinistului.

Restricții și precizări

• 1 ≤ n,m ≤ 20;
• înălțimile zonelor fi mai mici decât 100;
• alpinistul nu poate părăsi muntele și nu poate trece de două ori prin aceeași zonă;
• dacă nu există niciun traseu se va afișa imposibil.

Exemplu:

Intrare

4 5
4 5 3 8 9
8 7 7 8 9
9 7 3 9 10
2 5 4 10 11

Ieșire

10

Explicație

Un traeu de lungime maximă este:

1 2 - 6 7
- 3 4 5 8
- - - - 9
- - - - 10