{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tA maze of rectangular rooms is represented on a two dimensional grid as illustrated in figure 1a. Each point of the grid is represented by a character. The points of room walls are marked by the same character which can be any printable character different than `\u003ctt\u003e*\u003c/tt\u003e\u0026#39;, `\u003ctt\u003e_\u003c/tt\u003e\u0026#39; and space. In figure 1 this character is `\u003ctt\u003eX\u003c/tt\u003e\u0026#39;. All the other points of the grid are marked by spaces.\u003c/p\u003e\r\n\u003cpre\u003eXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXX\r\nX X X X X X X###X###X###X X X\r\nX X X X X###########X X X\r\nX X X X X X X###X###X###X X X\r\nXXXXXX XXX XXXXXXXXXX XXXXXX#XXX#XXXXXXXXXX\r\nX X X X X X X X###X###X###X###X\r\nX X * X X X###############X\r\nX X X X X X X X###X###X###X###X\r\nXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXX\r\n\u003c/pre\u003e\r\n\u003cdiv align\u003d\"CENTER\"\u003e\r\n\ta) Initial maze \u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; b) Painted maze\r\n\t\u003cp\u003e\r\n\t\tFigure 1. Mazes of rectangular rooms\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cp\u003e\r\n\tAll rooms of the maze are equal sized with all walls 3 points wide and 1 point thick as illustrated in figure 2. In addition, a wall is shared on its full length by the separated rooms. The rooms can communicate through doors, which are positioned in the middle of walls. There are no outdoor doors.\u003c/p\u003e\r\n\u003cpre\u003edoor\r\n |\r\n XX XX\r\n X . X measured from within the room\r\n door - ...-- walls are 3 points wide\r\n X . X__\r\n XXXXX |\r\n |___ walls are one point thick\r\n\u003c/pre\u003e\r\n\u003cdiv align\u003d\"CENTER\"\u003e\r\n\tFigure 2. A room with 3 doors\u003c/div\u003e\r\n\u003cp\u003e\r\n\tYour problem is to paint all rooms of a maze which can be visited starting from a given room, called the `start room\u0026#39; which is marked by a star (`\u003ctt\u003e*\u003c/tt\u003e\u0026#39;) positioned in the middle of the room. A room can be visited from another room if there is a door on the wall which separates the rooms. By convention, a room is painted if its entire surface, including the doors, is marked by the character `\u003ctt\u003e#\u003c/tt\u003e\u0026#39; as shown in figure 1b.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tThe program input is a text file structured as follows:\u003c/p\u003e\r\n\u003cdl compact\u003d\"compact\"\u003e\r\n\t\u003cdt\u003e\r\n\t\t1.\u003c/dt\u003e\r\n\t\u003cdd\u003e\r\n\t\tThe first line contains a positive integer which shows the number of mazes to be painted.\u003c/dd\u003e\r\n\t\u003cdt\u003e\r\n\t\t2.\u003c/dt\u003e\r\n\t\u003cdd\u003e\r\n\t\tThe rest of the file contains the mazes.\u003c/dd\u003e\r\n\u003c/dl\u003e\r\n\u003cp\u003e\r\n\tThe lines of the input file can be of different length. The text which represents a maze is terminated by a separation line full of underscores (`\u003ctt\u003e_\u003c/tt\u003e\u0026#39;). There are at most 30 lines and at most 80 characters in a line for each maze\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThe program reads the mazes from the input file, paints them and writes the painted mazes on the standard output.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tThe output text of a painted maze has the same format as that which has been read for that maze, including the separation lines. The example below illustrates a simple input which contains a single maze and the corresponding output.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\u003cspan style\u003d\"font-family:courier new,courier,monospace;\"\u003e2\r\nXXXXXXXXX\r\nX X X\r\nX * X\r\nX X X\r\nXXXXXXXXX\r\nX X\r\nX X\r\nX X\r\nXXXXX\r\n_____\r\nXXXXX\r\nX X\r\nX * X\r\nX X\r\nXXXXX\r\n_____\u003c/span\u003e\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\u003cspan style\u003d\"font-family:courier new,courier,monospace;\"\u003eXXXXXXXXX\r\nX###X###X\r\nX#######X\r\nX###X###X\r\nXXXXXXXXX\r\nX X\r\nX X\r\nX X\r\nXXXXX\r\n_____\r\nXXXXX\r\nX###X\r\nX###X\r\nX###X\r\nXXXXX\r\n_____\u003c/span\u003e\u003c/pre\u003e"}}]}