eolymp
bolt
Try our new interface for solving problems
Problems

Rubik`s Rectangle

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\textbf{H}×\textbf{W} frame with tiles with all numbers from \textbf{1} to \textbf{H·W} printed on them. \includegraphics{https://static.e-olymp.com/content/ab/abb57f081b13830b56a5ff344dc0e35f62a86c9a.jpg} The only type of move that is allowed is \textit{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{https://static.e-olymp.com/content/06/069977e3549407cdd3690bc205c29d4c77fb5886.jpg} 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{https://static.e-olymp.com/content/37/377f375798f4e4bc321564136cd6135b615cd185.jpg} \InputFile The first line of input contains the number of test cases \textbf{T}. 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 \textbf{W }and \textbf{H} (\textbf{1} ≤ \textbf{W}, \textbf{H} ≤ \textbf{100}) -- the width and height of the puzzle, respectively. Each of the next \textbf{H} lines contains \textbf{W} space-separated integers -- the numbers printed on consecutive tiles. \OutputFile 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 \textbf{POSSIBLE} or \textbf{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 \textbf{0}) and then their descriptions, each consisting of a single letter \textbf{R} or \textbf{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 \textbf{10·W·H} moves. Each test case is either solvable within this limit, or not solvable at all.
Time limit 5 seconds
Memory limit 256 MiB
Input example #1
4

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
Output example #1
POSSIBLE 1 R3
POSSIBLE 0
POSSIBLE 3 R3 C3 R2
IMPOSSIBLE
Source 2013 ACM ICPC Central Europe Regional Contest, Kraków, November 15-17, Problem A