Az S. 135. feladat (2019. május)

S. 135. Adott egy terület domborzati térképe, amelyre gondolatban egy \(\displaystyle N\times N\)-es négyzethálót terítünk. A négyzetháló minden négyzetéhez hozzárendelünk a térkép alapján egy magasság értéket. Szeretnénk bejárni a terület felét, azaz a négyzetek legalább felét (páratlan \(\displaystyle N\) esetén felső egészrészt véve). A bejárás során egy-egy négyzetről csak egy vele oldalszomszédos négyzetre tudunk átmenni, ha a két négyzet magasság értékének különbsége legfeljebb \(\displaystyle D\). Adjuk meg azt a legkisebb \(\displaystyle D\) értéket, amivel be tudjuk járni a terület legalább felét, ha a bejárás tetszőleges négyzetről indulhat.

Bemenet: az első sor tartalmazza az \(\displaystyle N\) számot; a következő \(\displaystyle N\) sor mindegyike \(\displaystyle N\) számot tartalmaz: az \(\displaystyle i\). sor \(\displaystyle j\). száma az \(\displaystyle i\). sor \(\displaystyle j\). négyzetének magasságértékét adja meg.

Kimenet: a legkisebb \(\displaystyle D\) egész szám, amivel megvalósítható a bejárás.

Korlátok: \(\displaystyle 1\le N\le 500\), \(\displaystyle 0\le \text{egy négyzet magassága}\le {10}^{6}\).

Időlimit: 0,3 mp.

Beküldendő egy s135.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztő környezetben futtatható.

(10 pont)

A beküldési határidő 2019. június 11-én LEJÁRT.

Statisztika:

4 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Noszály Áron, Szente Péter.
3 pontot kapott:	1 versenyző.

A KöMaL 2019. májusi informatika feladatai