Rubik's Rectangle

A new puzzle which aims to conquer the game market is a fusion of Rubik’s Cube and Fifteen. The board is an $H \times W$ frame with tiles with all numbers from $1$ to $H \cdot W$ printed on them.

\includegraphics[width=0.3\textwidth ]{img01}

The only type of move that is allowed is flipping either one of the rows or one of the columns. Flipping reverses the order of the row’s (or column’s) elements. Below the third row is flipped:

\includegraphics[width=0.3\textwidth ]{img02}

You are given a board with tiles numbered in some arbitrary order. Determine a sequence of flips that brings the board to the nicely sorted position, if possible.

\includegraphics[width=0.3\textwidth ]{img03}


The first line of input contains the number of test cases $T$, $1 \leq T \leq 63\, 161$. The descriptions of the test cases follow:

The description of each test case starts with an empty line. The next line contains two space-separated integers $W$ and $H$ ($1 \leq W, H \leq 100$)—the width and height of the puzzle, respectively. Each of the next $H$ lines contains $W$ space-separated integers$—$the numbers printed on consecutive tiles.


Print the answers to the test cases in the order in which they appear in the input. Start the output for each test case with the word POSSIBLE or IMPOSSIBLE, depending on whether it is possible to solve the puzzle. If a solution exists, print (in the same line) first the number of moves (possibly 0) and then their descriptions, each consisting of a single letter R or C specifying whether we are to flip a row or a column, concatenated with the index of the row or column to flip.

Any solution will be accepted as long as it does not use more than $10 \cdot W \cdot H$ moves. Each test case is either solvable within this limit, or not solvable at all.

Sample Input 1 Sample Output 1

3 3
1 2 3
4 5 6
9 8 7

4 2
1 2 3 4
5 6 7 8

4 4
1 2 15 4
8 7 11 5
12 6 10 9
13 14 3 16

3 4
1 2 4
3 5 6
7 8 9
10 11 12
CPU Time limit 10 seconds
Memory limit 1024 MB
Statistics Show
License For educational use only

Please log in to submit a solution to this problem

Log in