eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Новая головоломка, являющаяся объединением Кубика Рубика и Пятнашек, завоевывает игровой рынок. Она представляет собой доску H×W, на которой расположены плитки с написанными на них всеми числами от 1 до H·W.

Единственной разрешенной операцией является перевертывание либо одной строки, либо одного столбца. Перевертывание меняет порядок элементов строки (или колонки). Ниже приведен пример переворачивания третьей строки:

Задана доска, плитки которой пронумерованы в произвольном порядке. Определите последовательность перевертываний, которые переведут плитки в отсортированный вид.

Giriş verilənləri

Первая строка содержит количество тестов t. Каждый тест начинается с пустой строки. Следующая строка содержит два числа W и H (1 W, H 100) – ширина и высота головоломки. Следующие H строк содержат W целых чисел, записанных на последовательных плитках.

Çıxış verilənləri

Вывести ответ на каждый тест в отдельной строке. Первое слово должно быть POSSIBLE или IMPOSSIBLE в зависимости от того, можно ли решить головоломку. Если решение существует, вывести (в той же строке) количество перевертываний (возможно равное 0) и их описания, состоящих из одной буквы R или C (переворачивание строки или столбца), и индекса соответствующей строки или столбца.

Вывести следует любое правильное решение, состоящее из не более 10·W·H ходов. Каждый тест либо разрешим за указанное время, либо не имеет решения.

Nümunə

Giriş verilənləri #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
Çıxış verilənləri #1
POSSIBLE 1 R3
POSSIBLE 0
POSSIBLE 3 R3 C3 R2
IMPOSSIBLE
Mənbə 2013 ACM ICPC Central Europe Regional Contest, Краков, Ноябрь15-17, Задача A