Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1490. Головоломка "9 квадратов"
Генерация всех подмножеств, сочетаний, перестановокПоиск в ширину (BFS)
Олимпиадные задачи на русском языке
| 13/09/2010 | Заочный тур личного первенства (C) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Квадрат `3\ times\ 3` сложен из квадратных фишек `1\ times\ 1`. Фишки пронумерованы числами от 1 до 9.
Начальное расположение фишек показано ниже. Фишки каждого квадрата `2\ times\ 2` можно поворачивать на угол,
кратный 90 градусов.
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
Напишите программу, которая находит способ получения заданного расположения фишек из начального за наименьшее количество ходов.
Ввод содержит три строки, содержащих по три целых числа от 1 до 9 – требуемое расположение фишек.
В первой строке вывести одно целое число `K` – минимальное количество ходов.
Во второй строке вывести последовательность ходов через пробел.
Поворот левого верхнего квадрата `2\ times\ 2` на 90 по часовой стрелке обозначается A1, на 180 градусов – A2,
а на 90 против часовой стрелки – A3, для поворотов правого верхнего используются обозначения B1, B2
и B3, левого нижнего – C1, C2 и C3, правого нижнего – D1, D2 и D3.
Если существует несколько решений с наименьшим количеством ходов, то можно вывести одно из них (любое).
Пример ввода
2 5 3 1 8 4 7 9 6
Пример вывода
2 A3 D1
