[UVA] 782 - Contour Painting
Contour Painting
| Contour Painting |
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 XXXXXXX
5| XXXXXXXX XX
6| X X XXXXXXX
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:
####
### X### XXXX#
XXX XXXX X#
flat zone concave corner convex corner
Figure 2: Cases of point painting
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 XXXXXXXXXX interior
XXXX XX XXXX#######XX painting
X * X X### # ##X
X X XXXXXXX X######X# #XXXXXXX
XXXXXXXX XX XXXXXXXX# #######XX
X X XXXXXXX X######X# #XXXXXXX
X X X### # ##X
XXXX XX XXXX#######XX
XXXXXXXXXX XXXXXXXXXX
* ########## exterior
XXXXXXXXXX #XXXXXXXXXX## painting
XXXX XX #XXXX XX#
X X #X X######
X X XXXXXXX #X X XXXXXXX##
XXXXXXXX XX #XXXXXXXX XX#
X X XXXXXXX #X X XXXXXXX##
X X #X X######
XXXX XX #XXXX XX#
XXXXXXXXXX #XXXXXXXXXX##
##########
Figure 3: Painting a closed contour
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
X X
X X XXXXXXX
XXXXXXXX XX
X X XXXXXXX
X X
XXXX *XX
XXXXXXXXXX
__________
XXXXXXXXXX
* XXXX XX
X X
X X XXXXXXX
XXXXXXXX XX
X X XXXXXXX
X X
XXXX XX
XXXXXXXXXX
__________
Sample Output
XXXXXXX
X#####X
XXXXXXX
__________
XXXXXXXXXX
XXXX#######XX
X### # ##X
X######X# #XXXXXXX
XXXXXXXX# #######XX
X######X# #XXXXXXX
X### # ##X
XXXX#######XX
XXXXXXXXXX
__________
##########
#XXXXXXXXXX##
#XXXX XX#
#X X######
#X X XXXXXXX##
#XXXXXXXX XX#
#X X XXXXXXX##
#X X######
#XXXX XX#
#XXXXXXXXXX##
##########
__________
Miguel Revilla
2001-01-05
一直 PE 的原因來自於一開始就有空白尾行，
因此輸出得時候處理一下多餘的空白。
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
char g[100][100], star[100][100];
int idx;
void paintstar(int i, int j) {
if(i < 0 || j < 0 || i >= idx || j > 99) return;
if(!(g[i][j] == ' ' || g[i][j] == '\0'))
return;
if(star[i][j]) return;
star[i][j] = 1;
paintstar(i+1, j);
paintstar(i-1, j);
paintstar(i, j+1);
paintstar(i, j-1);
}
void paint(int i, int j) {
if(i < 0 || j < 0 || i >= idx || j > 99) return;
if(star[i][j]) {
if(g[i][j] == '\0') {
int tmp = j;
while(tmp >= 0 && g[i][tmp] == '\0')
tmp--;
tmp++;
while(tmp < j)
g[i][tmp] = ' ', tmp++;
g[i][j+1] = '\0';
}
g[i][j] = '#';
}
}
int main() {
int t, i, j;
scanf("%d", &t);
cin.ignore(100, '\n');
while(t--) {
memset(g, 0, sizeof(g));
memset(star, 0, sizeof(star));
idx = 0;
while(gets(g[idx])) {
if(g[idx][0] == '_')
break;
idx++;
}
for(i = 0; i < idx; i++)
for(j = 0; g[i][j]; j++)
if(g[i][j] == '*') {
g[i][j] = ' ';
paintstar(i, j);
}
for(i = 0; i < idx; i++) {
for(j = 0; g[i][j]; j++) {
if(g[i][j] != ' ' && g[i][j] != '#') {
paint(i+1, j);
paint(i-1, j);
paint(i, j+1);
paint(i, j-1);
}
}
}
for(i = 0; i <= idx; i++) {
j = strlen(g[i])-1;
while(j >= 0 && g[i][j] == ' ')
j--;
g[i][j+1] = '\0';
puts(g[i]);
}
}
return 0;
}