National Olympiad in Informatics, China, 2005
The wisdom beads game set consists of a triangular board and game pieces of varying shapes. The board is depicted in Figure 1, as follows:
Figure 1
The game pieces fall into major categories, depending on the number of beads they consist of.
For the 1st major category, there are beads, but only one type of shape:
The symbol is , the shape is
For the 2nd major category, there are beads and types of shapes:
The symbol is , the shape is
The symbol is , the shape is
The symbol is , the shape is
For the 3rd major category, there are beads and types of shapes:
The symbol is , the shape is
The symbol is , the shape is
The symbol is , the shape is
The symbol is , the shape is
The symbol is , the shape is
The symbol is , the shape is
The symbol is , the shape is
The symbol is , the shape is
Figure 2
Figure 2 depicts one method of piecing together the game board. The depiction in Figure 2 can be simplified to Figure 3, so the board can be expressed as a two-dimensional array of characters.
|
Figure 3 |
A piece may be placed at any location on the board, provided that there is room to place it, and that the dimensions are appropriate. Rotations (, , , and ) and flips (horizontal and vertical) are allowed for placing any of the pieces.
Given the initial setup of a game board, determine a valid method for placing all of the remaining pieces onto the board.
Input Specification
The input contains a total of lines, describing the initial game
board. Line contains characters. If the -th character of line
is a letter from A
to L
, then that means row column
has already been occupied by the game piece of the specified letter. If
the -th character of line is the character .
, then that means
row column is currently empty.
Output Specification
If it's possible to find a solution, print lines to the output - the
game board after all pieces have been placed. The -th line must
contain characters, where the -th character of the -th line is
the symbol of the piece that occupies the board at that location.
If there's no solution, output a single line with the string No
solution
.
The data guarantees that there will be at most one solution for each
test case.
Sample Input
.
..
...
....
.....
.....C
...CCC.
EEEHH...
E.HHH....
E.........
Sample Output
B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF
Problem translated to English by .
Comments