Problem S. 43. (March 2009)
S. 43. We are given a rectangular labyrinth. Its walls are unit squares and it has one entrance from which each square of the labyrinth can be reached. Corridors and walls are parallel with the outer walls, and it may be the case that there is more that one path between two given points.
We would like to illuminate each square of the labyrinth by placing lamps on the ceiling of the corridors. A lamp illuminates the complete horizontal or vertical corridor segments in which the lamp is located. Your task is to illuminate the complete labyrinth by using the minimal number of lamps.
In the example, ``Bemenet'' is ``input'', while ``Kimenet'' is ``output''.
The first command line argument of your program solving this problem is the name of the input text file containing the plan of the labyrinth, while the second command line argument is the name of the output text file that should contain the solution. The input file has at most 100 lines. Each line has the same number of consecutive 0s or 1s: 0 means corridor and 1 is wall. The structure of the output file should be similar, and the position of the lamps should be marked with X. The total number of lamps should also be displayed on the screen. When evaluating your solution, running time for various labyrinth sizes will be taken into account, and some points will be awarded for solutions with slightly more than optimal number of lamps.
The source code of your program (s43.pas, s43.cpp, ...) and a short documentation (s43.txt, s43.pdf, ...) should be submitted, also describing your solution and specifying the name of the developer environment to use for compiling.
(10 pont)
Deadline expired on April 15, 2009.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
16 students sent a solution. 10 points: Englert Péter, Lájer Márton, Weisz Ágoston. 9 points: Nagy Róbert. 8 points: 1 student. 7 points: 1 student. 6 points: 8 students. 4 points: 2 students.
Problems in Information Technology of KöMaL, March 2009