sí

A fenti kép egy hegyvidéki terep domborzati térképe mátrix formában. A számok az adott hely magasságát jelentik. Síelni akarunk és minél hosszabb jó utat keresünk a terepen. Egy utat jó-nak nevezünk ha az egymás utáni helyek vízszintes vagy függőleges irányban (diagonálisan nem!) szomszédosak benne és a magasság minden lépésben szigorúan csökken. Az ábrán a 11-ből induló zöld nyíllal jelölt út a (2,4),(2,5),(2,6),(3,6),(3,5),(4,5),(4,4),(4,3) helyek sorozata, ahol az első számok a sor, a második számok az oszlop sorszámát jelentik. Könnyen látható, hogy ez egy jó út, ahogyan az ábrán levő piros is az. Az út hosszán az érintett helyek (darab)számát értjük, az ábrán a zöld út 8, a piros 7 hosszú.

Feladat: számoljuk ki a leghosszabb jó út L hosszát.

A bemenet specifikációja

R C
t11 ... t1C
t21 ... t2C
...
tR1 ... tRC

Az első sorban az 1 ≤ R,C ≤ 100 szóközzel elválasztott számok a térkép sorainak és oszlopainak számát jelölik. A következő R sor mindegyike C szóközzel elválasztott pozitív számot tartalmaz, melyek nem nagyobbak mint 106 .

A kimenet specifikációja

L

Egyetlen sor a leghosszabb jó út L hosszával.

1. példa bemenet

1. 2 2
2. 1 2
3. 3 4

letöltés szöveges állományként

1. példa kimenet

1. 3

letöltés szöveges állományként

2. példa bemenet

1. 3 4
2. 1 2 3 3
3. 4 5 4 2
4. 7 6 5 6

letöltés szöveges állományként

2. példa kimenet

1. 7

letöltés szöveges állományként

3. példa bemenet

1. 4 6
2. 3 5 7 4 4 2
3. 4 3 9 11 8 7
4. 1 2 4 8 5 6
5. 4 1 1 2 3 10

letöltés szöveges állományként

3. példa kimenet

1. 8

letöltés szöveges állományként