Az I/S. 20. feladat (2017. október)

I/S. 20. Egy elektromos terepjáró autóval szeretnénk eljutni egy dimbes-dombos területen az egyik helyről a másikra. A területet gondolatban \(\displaystyle N \times M\) egyforma négyzetre osztjuk, és minden egyes négyzethez egy magassági adatot rendelünk. A négyzetek számozása a bal felső saroktól indul jobbra, illetve lefelé. Az autó útját úgy modellezzük, mintha egy-egy oldalukkal egymással érintkező négyzeteken haladna keresztül. Az egyik négyzetről a másikra történő mozgáskor az autó 1 egységnyit meríti az akkumulátorát, ha a két négyzet azonos magasságban van. Alacsonyabb magasságban lévő négyzetről magasabban lévő négyzetre mozgáskor a szintkülönbség kétszerese plusz 1 egységnyit merül az akkumulátor. Amikor az autó lefelé halad, akkor a szintkülönbség számértékének megfelelő egységnyit töltődik az akkumulátor, miközben 1 egységet merül. Az autó indulási pontja a térkép \(\displaystyle (s_i, s_j)\) négyzete, a cél a térkép \(\displaystyle (c_i, c_j)\) négyzete.

Kérdés, hogy legkevesebb hány egységnyi töltéssel kell rendelkeznie az autónak a kiindulási négyzetben, hogy eljusson a cél négyzetbe úgy, hogy közben egyszer sem kell külső energiával tölteni, csupán a szintkülönbség csökkenésekor kap energiát. Az autó nem tud továbbmenni, ha egy négyzetbe érve nem pozitív az energiája, ezért az csak a cél négyzetben lehet 0.

A feladatot megoldó program olvassa be a standard bemenetről a térképhez tartozó \(\displaystyle N\) és \(\displaystyle M\) értékét, majd a következő \(\displaystyle N\) sor mindegyikében \(\displaystyle M\) pozitív egész \(\displaystyle h_{i,j}\) számot, melyek a térkép \(\displaystyle i\)-edik sorában és \(\displaystyle j\)-edik oszlopában lévő négyzet szintértékét adják, illetve a következő sorban az induló és cél négyzetek adatait: \(\displaystyle s_i\), \(\displaystyle s_j\), \(\displaystyle c_i\), \(\displaystyle c_j\). A program írja a szabványos kimenetre a legkisebb akkumulátor töltöttséget, amellyel az autó a kiindulási helyről a célba érhet.

Példa:

4 5  
1 2 4 3 4 
1 1 3 5 2
1 3 2 3 4
1 2 1 1 3
3 2 1 4

7

Korlátok: \(\displaystyle 1 \le N, M \le 100\), \(\displaystyle 1 \le h_{i,j} \le 1000\).

Értékelés: a megoldás lényegét leíró dokumentáció 1 pontot ér. További 9 pont kapható arra a programra, amely a korlátoknak megfelelő bemenetekre helyes kimenetet ad 1 másodperc futásidő alatt. Részpontszám kapható arra a programra, amely csak kisebb \(\displaystyle N\) és \(\displaystyle M\) értékek esetén ad helyes eredményt 1 másodpercen belül.

Beküldendő egy is20.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja.

(10 pont)

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

A megoldások döntően a Dijkstra-algoritmust alkalmazták útvonalkeresésre adott töltöttség esetén, míg a töltöttség értékét bináris kereséssel változtatták.

Mintamegoldásként Gáspár Attila (IS20ga.cpp) és Horcsin Bálint ( dokumentaciohb.txt, is20hb.java) megoldásait közöljük.

A tesztesetek és a helyes kimenetek: tesztek.zip

Statisztika:

10 dolgozat érkezett.
10 pontot kapott:	Gáspár Attila, Horcsin Bálint, Janzer Orsolya Lili, Noszály Áron.
9 pontot kapott:	Horváth Botond István.
8 pontot kapott:	1 versenyző.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	2 versenyző.
4 pontot kapott:	1 versenyző.

A KöMaL 2017. októberi informatika feladatai