2277 -- Region Filling

Language:

Region Filling

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 453		Accepted: 68

Description

This problem is to write a program to fill a region in a rectangular array of pixels given the outline of the region.

Input

The input is a sequence of problem instances. Each problem instance begins with a line containing the row-count of the array, the column-count of the array and the number-of-regions to fill as decimal integers. Rows are counted from top to bottom beginning with 1. Columns are counted from left to right beginning with 1. The input ends with a row-count of 0. Row-count will be at most 47 and column-count will be at most 63.

The first line of each problem instance is followed by region descriptions for number-of-regions regions. Each region description begins with a line containing: a single character to be used to fill the region, the row number of the start pixel, the column number of the start pixel and the number of pixels in the boundary which will always be at least two. The region fill character will be distinct for each region within a problem instance. This line is followed by lines of direction codes (up = A, up right = B, etc.):

describing the outline traversed clockwise. The start pixel may be any point on the outline.

Output

For each problem instance, the output consists of row-count lines of column-count characters each of which is either a period (.) indicating than no region includes that pixel or the fill character of the region which includes that pixel. The row-count lines are followed by a single blank line. This array may be preceded by one or more lines of the following form (where A or B are the fill characters specified in the region header):

REGION A GOES OUTSIDE THE ARRAY

If the boundary path goes outside the boundaries of the array specified for the problem instance.

REGION A BOUNDARY IS NOT CLOSED

If the boundary as specified does not return to the start point.

REGION B BOUNDARY INTERSECTS REGION A

If the boundary of region B contains points of a previously specified region. If a previous region fails any of these tests it is not considered for intersection with following regions.

For each region, the first condition to be violated is to be displayed. Any region for which an error line is given will not be filled in the rectangular array.

Sample Input

20 40 4
B 3 21 22
CCDDDCBBBCCFFFFFGHHHHH
C 5 8 36
CCDCDDDEDEEFEFFFGFGGHGHHHAHAABABBBCB
D 10 24 38
CCCCCCEEEGGFEDCCEEEGGGGGGAAACCBAHGGAAA
A 2 2 3
CEH
10 20 4
A 4 6 10
GGAAACCEEE
B 6 16 30
CCCCCCCCCCCCEEEGGGGGGGGGGGGAAA
C 5 6 10
CCCCDDFFFG
D 6 2 10
AAACCEEEGG
0 0 0

Sample Output

........................................
.AA.....................................
..A.................BBB......BBB........
.....................BBB....BBB.........
.......CCC............BBB..BBB..........
.....CCCCCCC...........BBBBBB...........
....CCCCCCCCC...........BBBB............
...CCCCCCCCCCC...........BB.............
..CCCCCCCCCCCCC.........................
..CCCCCCCCCCCCC........DDDDDDD..........
.CCCCCCCCCCCCCCC.......DDDDDDD..........
.CCCCCCCCCCCCCCC.......DDDDDDD..........
.CCCCCCCCCCCCCCC.......DDDDDDD..........
..CCCCCCCCCCCCC...........D.............
..CCCCCCCCCCCCC...........D.............
...CCCCCCCCCCC.........DDDDDDD..........
....CCCCCCCCC..........DDDDDDD..........
.....CCCCCCC...........DDDDDDD..........
.......CCC.............DDDDDDD..........
........................................

REGION B GOES OUTSIDE THE ARRAY
REGION C BOUNDARY IS NOT CLOSED
REGION D BOUNDARY INTERSECTS REGION A
...AAA..............
...AAA..............
...AAA..............
...AAA..............
....................
....................
....................
....................
....................
....................

Source

Greater New York 2004