The 4x4 game is played on a checkered board
having 5 rows and 5 columns. The squares are numbered left to right, top to
bottom. The squares with numbers 3, 11, 13, 15, and 23 are removed. So, the
game board has four 2x2 corner blocks with bridges between them.
There are 16 game pieces on the field, four
of each color: red, blue, yellow, and green. Initially, the pieces are placed
in the corner blocks (i. e. the squares numbered 8, 12, 14, and 18 are empty).
The objective is to move the pieces so that
all the pieces of each color were in the same corner block. A piece may only be
moved to an empty square immediately to the right, to the left, above, or
below. It is forbidden to move a piece to a square that is occupied by another
piece, or to a removed square.
Your task is to write a program that, given
the initial game position, will build a sequence of moves leading to the final
position with pieces of the same color grouped in the corner blocks.
Note: such a sequence always exists,
moreover, it is not unique. Any sequence of no more than 10,000 moves leading
to the final position will be considered as a correct solution. The sequence
does not have to be optimal.
Limitations
The resulting sequence may not be longer
than 10 000 moves.
Input
The input file contains 5 lines of 5
characters each describing the initial position on the game board. The first
line represents (left to right) the squares 1, 2, 3, 4, 5; the second line
represents the squares 6, 7, 8, 9, 10 and so on. Period characters (.) stand
for empty fields, X for removed fields, and R, B, Y and G for pieces
of different colors.
Output
The output file should contain a sequence
of moves resulting in the final position. Each move is represented on a
separate line with two space-delimited integers: the number of the initial
square and the number of the destination square.
Example
|
Input
|
Output
|
|
RRXGG
RG.YG
X.X.X
BR.BY
BBXYY
|
7 8
9 14
19 18
17 12
8 9
14 19
18 17
12 7
|
