eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Прямоугольник Рубика

Прямоугольник Рубика

Новая головоломка, являющаяся объединением Кубика Рубика и Пятнашек, завоевывает игровой рынок. Она представляет собой доску \textbf{H}×\textbf{W}, на которой расположены плитки с написанными на них всеми числами от \textbf{1} до \textbf{H·W}. \includegraphics{https://static.e-olymp.com/content/ab/abb57f081b13830b56a5ff344dc0e35f62a86c9a.jpg} Единственной разрешенной операцией является перевертывание либо одной строки, либо одного столбца. Перевертывание меняет порядок элементов строки (или колонки). Ниже приведен пример переворачивания третьей строки: \includegraphics{https://static.e-olymp.com/content/06/069977e3549407cdd3690bc205c29d4c77fb5886.jpg} Задана доска, плитки которой пронумерованы в произвольном порядке. Определите последовательность перевертываний, которые переведут плитки в отсортированный вид. \includegraphics{https://static.e-olymp.com/content/37/377f375798f4e4bc321564136cd6135b615cd185.jpg} \InputFile Первая строка содержит количество тестов \textbf{t}. Каждый тест начинается с пустой строки. Следующая строка содержит два числа \textbf{W }и \textbf{H} (\textbf{1 }≤ \textbf{W}, \textbf{H }≤ \textbf{100}) -- ширина и высота головоломки. Следующие \textbf{H }строк содержат \textbf{W} целых чисел, записанных на последовательных плитках. \OutputFile Вывести ответ на каждый тест в отдельной строке. Первое слово должно быть \textbf{POSSIBLE} или \textbf{IMPOSSIBLE} в зависимости от того, можно ли решить головоломку. Если решение существует, вывести (в той же строке) количество перевертываний (возможно равное \textbf{0}) и их описания, состоящих из одной буквы \textbf{R} или \textbf{C }(переворачивание строки или столбца), и индекса соответствующей строки или столбца. Вывести следует любое правильное решение, состоящее из не более \textbf{10·W·H} ходов. Каждый тест либо разрешим за указанное время, либо не имеет решения.
Лимит времени 5 секунд
Лимит использования памяти 256 MiB
Входные данные #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
Выходные данные #1
POSSIBLE 1 R3
POSSIBLE 0
POSSIBLE 3 R3 C3 R2
IMPOSSIBLE
Источник 2013 ACM ICPC Central Europe Regional Contest, Краков, Ноябрь15-17, Задача A