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##
                                                ##########

before painting after painting

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;
}

我要檢舉

#782#Contour Painting

台長： Morris

您可能對以下文章有興趣

[UVA] 12149 - Feynman

[UVA][TSP] 11405 - Can U Win?

[UVA][priority_queue] 11926 - Multitasking

[UVA][線段樹] 10587 - Mayor's posters

人氣(709) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][線段交] 10902 - Pick-up Sticks
此分類上一篇:[UVa][日期計算][JAVA] 11356 - Dates

回應(0)