Az S. 43. feladat (2009. március)

S. 43. Egy téglalap alaprajzú labirintus folyosói és falai egységnyi vastagságúak. A labirintusba egy bejárat van valamelyik oldalon, ahonnan a labirintus bármely pontjába el lehet jutni. A folyosók és a falak a labirintus oldalfalaival párhuzamosan haladnak, előfordulhat, hogy egy pontból egy másikba több út is vezet.

A labirintust szeretnénk úgy megvilágítani, hogy mindegyik részébe jusson fény valamelyik lámpából. A labirintus folyosóinak mennyezetére elhelyezett lámpák az elhelyezési ponthoz csatlakozó (egyenes) folyosószakaszokat azok teljes hosszában megvilágítják. A kérdés csupán az, hogy hová helyezzük el a lámpákat, hogy a lehető legkevesebb lámpával megoldjuk a teljes megvilágítást.

A kérdésre választ adó program az első parancssori argumentumaként megadott szöveges állományból olvassa be a labirintus alaprajzát, és a második argumentumaként megadott szöveges állományba írja ki a megoldást. A bemeneti állomány legfeljebb 100 sorában soronként azonos számú, legföljebb 100 darab ,,0'' vagy ,,1'' szerepel egymás mellett: a ,,0'' a folyosót, az ,,1'' pedig a falat jelöli a labirintus négyzethálós térképén. A kimeneti állományban a bemeneti állományhoz hasonlóan jelöljük a falakat és folyosókat, valamint egy-egy ,,X'' szerepeljen minden lámpa helyén. A képernyőre írjuk ki a szükséges lámpák számát. Az értékelésnél figyelembe vesszük a programok futási sebességét kisebb-nagyobb labirintusokra, illetve részpontszámot adunk az egyes esetekben az optimálisnál több lámpát felhasználó megoldásokra is.

Beküldendő a program forráskódja (s43.pas, s43.cpp, ...), valamint a program rövid dokumentációja (s43.txt, s43.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztőkörnyezetben fordítható.

(10 pont)

A beküldési határidő 2009. április 15-én LEJÁRT.

Mintamegoldásként Weisz Ágoston, 10. osztályos budapesti diák C# nyelven készített programját (s43.cs) és Englert Péter 10. osztályos zalaegerszegi versenyző Pascal programját (S43.pas) adjuk közre. Mindkettő jól kommentezett, érthető forrás.

A beküldött megoldásokat az alábbi tesztállományokkal vizsgáltuk: s43forras.zip

A labirintusok egy része "furcsa" volt, előfordultak benne a bejárattól elérhetetlen részek, sőt izolált pont is. Természetesen nem vettük hibának azt, ha valaki ezekbe "nem jutott el".

A versenyzők többsége a szükségesnél több lámpa elhelyezésével oldotta meg a feladatot, ők legföljebb 6 pontot kaptak.

Statisztika:

16 dolgozat érkezett.
10 pontot kapott:	Englert Péter, Lájer Márton, Weisz Ágoston.
9 pontot kapott:	Nagy Róbert.
8 pontot kapott:	1 versenyző.
7 pontot kapott:	1 versenyző.
6 pontot kapott:	8 versenyző.
4 pontot kapott:	2 versenyző.

A KöMaL 2009. márciusi informatika feladatai