Region Filling

Time limit1sMemory limit128 MB

Summary

Trace region boundaries from direction strings, validate them for out-of-bounds moves, closure, and overlaps, then flood-fill each closed boundary with its letter.

Level: Medium6 of 10
Topics: Simulation, Implementation, Array
Solved: No attempts yet

Problem

Several region boundaries are given. Write a program that fills each boundary and its interior with the region letter, then prints the completed grid.

Input

The first line contains the number of test cases.

For each test case, the first line contains the number of rows R, the number of columns C, and the number of regions. Rows are numbered from top to bottom starting at 1, and columns are numbered from left to right starting at 1. There are at most 47 rows and at most 63 columns.

Each region is described by two lines. The first line gives the letter used to fill the region, the starting row and column of the boundary, and the boundary length. The boundary length is at least 2. Region letters are distinct. The next line contains the direction string for the boundary.

Each direction character means the following neighboring cell relative to the current cell.

H A B
G   C
F E D

The direction string starts at the given cell and follows the boundary clockwise.

Output

For each test case, print R lines of C characters. Cells belonging to a region are printed with that region letter, and cells belonging to no region are printed as a period (.).

If any of the following errors occurs, print one line for each error, in the order the errors occur, before printing the completed grid. Replace A and B below with the actual region letters.

If a boundary goes outside the array, print:

REGION A GOES OUTSIDE THE ARRAY

If a boundary is not closed because it does not return to its starting cell, print:

REGION A BOUNDARY IS NOT CLOSED

If the boundary of region B overlaps a previously filled region A, print:

REGION B BOUNDARY INTERSECTS REGION A

Separate consecutive test cases with one blank line.

Examples1

Example 1

Input

2
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

Expected 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..............
....................
....................
....................
....................
....................
....................