Programozó versenyek

DEIK Regionális Programozó Csapatverseny, középiskolai kategória, 2022. december 4.

2022. december 4. 10:00 – 2022. december 4. 15:15

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 utat keresünk a terepen. Egy utat -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 ú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 ú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 ú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
Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.