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

Intellectual Property

Intellectual Property

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Эраст Копи - известный дизайнер головоломки Судоку. Оглушительный успех сборникам его головоломок обеспечил ряд подражаний и плагиата. Перед отправкой в суд он решил получить больше доказательств. Головоломка Судоку представляет собой таблицу 9 × 9, разделенную на подтаблицы 3 × 3, каждая из которых содержит 3 × 3 ячеек. В каждой ячейке может находиться цифра от 1 до 9. Задача состоит в заполнении пустых ячеек цифрами таким образом чтобы каждая строка, столбец и каждая из 9 подтаблиц 3 × 3 содержала каждую цифру от 1 до 9 только один раз.

У Koпи есть база данных головоломок Судоку, и он хочет проверить, содержит ли она подобные головоломки. Головоломка P похожа на головоломку Q, если можно превратить головоломку P в головоломку Q, используя следующую последовательность операций:

  • выбрать две цифры x и y и заменить все цифры x на y и наоборот;

  • переставить две тройки строк: (1, 2, 3), (4, 5, 6), (7, 8, 9);

  • переставить две строки в одной тройке строк;

  • переставить две тройки стобцов: (1, 2, 3), (4, 5, 6), (7, 8, 9);

  • переставить два столбца в одной тройке столбцов;

  • flip along top-left - bottom-right axis. After this operation columns become rows and vice versa.

prb6268

Помогите Копи найти подобные задачи в его базе данных.

Входные данные

The first line contains single integer n (1n20) - the number of puzzles in the database.

The rest contains description of n puzzles: P[1], P[2], ..., P[n]. Each puzzle is described by nine lines that contain nine characters each. Each character is either a digit from 1 to 9, or a dot ('.') denoting an empty cell. An empty line separates consecutive puzzles in the database.

There are no spaces in the input data.

The puzzles are not guaranteed to be solvable.

Выходные данные

Check if the puzzle P[1] is similar to puzzles P[2], P[3], ..., P[n] (in this order), than check if the puzzle P[2] is similar to puzzles P[3], P[4], ..., P[n] (in this order) and so on.

If the puzzle P[i] is similar to the puzzle P[j] (1i < jn) output "Yes", otherwise output "No". If the answer is positive, the next line should contain an integer q[ij] - the number of operations required to transform the puzzle P[i]to the puzzle P[j]. The number of operations is not required to be minimal, however it must not exceed 1000. In the following q[ij] lines write the operations that transform the puzzle P[i] to the puzzle P[j], one per line.

Операции кодируются следующим образом:

  • "D x y" для обмена цифрами x и y;

  • "R a b" для обмена троек строк (3a-2, 3a-1, 3a) и (3b-2, 3b-1, 3b);

  • "r a b" for swapping rows a and b, rows must belong to same triple of rows;

  • "C a b" for swapping triples of columns (3a-2, 3a-1, 3a) and (3b-2, 3b-1, 3b);

  • "c a b" for swapping columns a and b, columns must belong to same triple of columns;

  • "F" for flipping along top-left - bottom-right axis.

Столбцы нумеруются слева направо, а строки нумеруются сверху вниз как они даны во входных данных, начиная с первой.

Пример

Входные данные #1
4
.....1...
1........
.2.....8.
.........
8....9...
.........
....7....
...2...1.
2...4....

....2....
...7.4...
8.......9
.8...2..1
..2......
.........
.........
..1.8....
.........

1........
.........
.........
.........
.........
.........
.........
.........
.........

.....1...
1........
.2.....8.
.........
8....9...
.........
....7....
...2...1.
2...4....
Выходные данные #1
Yes
7
F
R 1 2
r 7 9
c 5 6
c 4 5
C 2 3
D 1 8
No
Yes
2
r 4 6
c 7 9
No
Yes
7
F
R 2 3
r 4 5
r 5 6
c 7 9
C 1 2
D 1 8
No
Источник 2013 ACM NEERC, Northern Subregional Contest, St Petersburg, October 26