Az S. 101. feladat (2015. október)

S. 101. Adott egy hegység térképe, pontosabban egy \(\displaystyle N\times M\)-es táblázat az egyes koordináták magasságával, melyek egyike sem nagyobb, mint \(\displaystyle 1\,000\,000\,000\). Továbbá adott néhány nagyon szép hely a hegységben. Azt szeretnénk eldönteni, hogy legalább mennyire nehéz az a túra, amely minden szép helyet meglátogat valamelyik szép helyről kiindulva. Azaz formálisan a legkisebb \(\displaystyle C\) számot szeretnénk meghatározni, hogy bármelyik szép helyről bármelyik másikra el lehessen jutni úgy, hogy közben a térképen egy mezőről mindig egy másik olyan élszomszédos mezőre lépünk, melyek szintkülönbsége legföljebb \(\displaystyle C\).

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle M\)-et, a térkép sorainak és oszlopainak számát (\(\displaystyle 1\le N, M\le 800\)), majd a következő \(\displaystyle N\) sorból soronként \(\displaystyle M\) db egészet: a magasságokat. Az utána következő \(\displaystyle N\) sorból is soronként \(\displaystyle M\) db egészet, melyek 0-k, vagy 1-ek lehetnek: 0, ha nem szép a hely, és 1, ha szép. A program írja a standard output első és egyetlen sorába a lehető legkisebb megfelelő \(\displaystyle C\) számot.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Beküldendő egy tömörített s101.zip állományban a program forráskódja az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja, amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2015. november 10-én LEJÁRT.

Statisztika:

22 dolgozat érkezett.
10 pontot kapott:	Bálint Martin, Csenger Géza, Fuisz Gábor, Gáspár Attila, Gergely Patrik, Janzer Orsolya Lili, Németh 123 Balázs, Noszály Áron, Zalavári Márton, Zarándy Álmos.
9 pontot kapott:	Alexy Marcell.
8 pontot kapott:	1 versenyző.
7 pontot kapott:	1 versenyző.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	3 versenyző.
3 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2015. októberi informatika feladatai