Feladat: S.43 Korcsoport: - Nehézségi fok: -
Füzet: 2009/március, 168. oldal  PDF  |  MathML 
Témakör(ök): Nehezebb feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

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ó.