A contour of points is represented on a two dimensional (2D) grid as illustrated in figure 1. The points of the contour are specified by the same character which can be any printable character, different than ‘*’,‘#’,‘ ’ and space. In figure 1 this character is ‘X’. All the other points of the grid are represented by spaces. The contour is connected, i.e. any two points on the contour can be reached from one another by traveling vertically, horizontally and diagonally. Moreover, it is considered that a contour can close a single non empty zone of grid points. 012345678901234567890123456789 ------------------------------ 0| 1| XXXXXXXXXX 2| XXXX XX 3|X X 4| X X 5| XXXXXXXX 6| X X 7|X X 8| XXXX XX 9| XXXXXXXXXX 0| Figure 1: A contour on a 2D grid The character ‘#’ represents the colour used to paint the contour as illustrated in figure 3. The paint is added on one side of the contour in such a way that each contour point of the painted side has at least one ‘#’ neighbour horizontally or vertically as shown in figure 2:
flat zone X### XXXX concave corner Figure 2: Cases of point painting
convex corner XXXXXXX XX XXXXXXX A contour can be painted either from inside or from outside. The painting side is specified by the presence of the character ‘’ inside or outside the contour as shown in figure 3. Notice that the star is removed from the grid once the painting is done. XXXXXXXXXX XXXX XX X X XXXXXXXXXX interior XXXX#######XX painting X######X X X XXXXXXXX X X X XXXXXXX XX XXXXXXX X X######X# XXXXXXXX# X######X# #XXXXXXX #######XX #XXXXXXX X#### ##X
XXXX XX XXXXXXXXXX
XXXXXXXXXX 2/4 XXXX X X XX X XXXXXXX XX XXXXXXX X XX before painting Figure 3: Painting a closed contour X X #XXXX #X #X XX# X###### XXXXXXX## XX# XXXXXXX## X###### XX# X XXXXXXXX X #XXXXXXXX XXXX XXXXXXXXXX #XXXX #XXXXXXXXXX## X #X #X X Your problem is to write a program which: reads from a text file a number n and n grids, each grid containing a single contour and a single star, paints each grid according to the position of the star and outputs the painted grids to a text file. Each contour is placed on its grid in such a way that it is fully surrounded by free grid points (spaces). Input The first line of the input text file contains the number of grids to be painted. The next lines of the file contain the grids. The lines which represent a grid are terminated by a separation line full of underscores (‘ ’). There are at most 30 lines and at most 80 characters in a line for each grid. The lines can be of different length. Output The standard output file contains the grids with the painted contours and with the stars removed. Each grid is output in the same format it has been read from the input file, including the separation line. It follows an example of the input and the output of the program for a single simple contour. Sample Input 3 XXXXXXX X*X XXXXXXX
XXXXXXXXXX XXXX XX XX X X XXXXXXX XXXX#######XX XXXXXXXXXX ########## #XXXXXXXXXX## exterior painting ########## after painting
3/4 XXXXXXXX XX X X XXXXXXX XX XXXX *XX XXXXXXXXXX
XXXXXXXXXX XXXX XX XX X X XXXXXXXX X X XXXXXXX XX XXXXXXX XX XXXX XX XXXXXXXXXX
Sample Output XXXXXXX X#####X XXXXXXX
XXXXXXXXXX
XXXX#######XX
X### # X######X# XXXXXXXX# X######X# X### # ##X #XXXXXXX #######XX #XXXXXXX ##X XXXX#######XX XXXXXXXXXX
##########
#XXXXXXXXXX##
#XXXX #X #XX #XXXXXXXX #XX #X #XXXX XX# X###### XXXXXXX## XX# XXXXXXX## X###### XX# #XXXXXXXXXX## ##########
4/4