Puzzle
Memory limit: 32 MB
The king of Byteland has received a gift, a jigsaw puzzle.
The puzzle consists of a board of size .
The field in the -th row and -th column ()
has coordinates and contains a piece with the number ,
.
Each of the numbers appears on exactly one of the
pieces.
Coordinates of the fields
To solve the puzzle, you have to put the pieces in order, so that
for each the field contains
the piece with number .
The following moves are allowed to solve the puzzle:
-
a cyclic shift of all pieces in a row a certain number of fields
to the right,
-
a cyclic shift of all pieces in a column a certain number of fields
down.
The king of Byteland managed to solve his puzzle, but he is not sure if
he would be able to solve it starting from a different initial
configuration.
Help him to solve this problem.
Task
Write a program that:
-
Reads from the standard input the description of the initial
configuration of the puzzle.
-
Finds out if the pieces on the board can be put in order using
only the moves given above. If the solution is possible,
the program should find the moves putting the pieces in order.
-
Writes the result to the standard output.
Input
In the first line of the standard input there is one integer -
the size of the board side
().
The following lines contain the description of the initial
configuration.
The line contains integers
separated by single spaces.
Output
If there is no solution, the program should write to the standard output
only one line containing only one word NO.
If a solution exists, the first line should contain one integer -
the number of moves leading to the solution of the puzzle. The number of
moves in your solution must not exceed .
The following lines
should contain the descriptions of the moves, one move per line.
Each such line should consist of a letter R
(for shifting a row to the right) or
C (for shifting a column down), a space,
and two integers: and
separated by a space; , .
A line containing R describes a cyclic shift of the
-th row fields to the right.
Such a move leads to the following board configuration:
Similarly, a line containing
C describes a cyclic
shift of the
-th column
fields down.
If there are several possible solutions, your program should output
anyone of them.
Example
For the input data:
4
4 6 2 3
5 10 7 8
9 14 11 12
13 1 15 16
the correct result is:
2
C 2 1
R 1 3
The above sequence of moves gives the following sequence of
configurations:
4 | 6 | 2 | 3 |
5 | 10 | 7 | 8 |
9 | 14 | 11 | 12 |
13 | 1 | 15 | 15 |
4 | 1 | 2 | 3 |
5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 |
1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 |
Task author: Rafał Rusin.