Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1355. Кубик Ьубика
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 04/10/2003 | Личное первенство университета по программированию (3) |
| 27/02/2010 | Занятие 8 (E) |
| 02/12/2023 | Марафон 80 задач, 7 этап (B) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
На последнем чемпионате мира по сборке кубика Рубика был установлен новый мировой рекорд. Программист Dan Knights собрал кубик всего за 20 секунд. Таких потрясающих результатов ему удалось добиться при помощи собственной программы, которая для любого начального состояния кубика выдавала оптимальную последовательность действий для сборки кубика. Конечно, он использовал эту программу только для подготовки к соревнованиям, так как она работала довольно долго.
В этой задаче вы должны написать аналогичную программу для кубика Ьубика, который устроен гораздо проще кубика Рубика. Кубик Ьубика состоит из восьми единичных кубиков, соединенных центральным механизмом в куб размером 2x2x2. Любую половину кубика Ьубика (верхнюю, нижнюю, левую, правую, переднюю или заднюю) можно поворачивать относительно другой на угол, кратный 90 градусов. Четыре единичных кубика в головоломке целиком покрашены в черный цвет, а четыре других – целиком в белый цвет. Кубик считается собранным, если его можно разделить плоскостью на две части (по 4 кубика), каждая из которых окрашена в свой цвет.
Из всех возможных манипуляций с кубиком удобнее всего использовать следующие шесть:
- CW – поворот всего кубика по часовой стрелке;
- CCW – поворот всего кубика против часовой стрелки;
- LU – поворот левой половины кубика вверх;
- LD – поворот левой половины кубика вниз;
- RU – поворот правой половины кубика вверх;
- RD – поворот правой половины кубика вниз.
При повороте RU кубик 2 переходит на место кубика 4, кубик 4 – на место кубика 8, 8 – на 6, а 6 – на 2.
Ввод
Во входном файле содержится одна строка из восьми символов B и W. Символ B означает черный цвет, а символ W – белый; `i`-й символ строки соответствует цвету `i`-го кубика (нумерация кубиков показана на рисунке). Строка содержит 4 символа B и 4 символа W.
Вывод
В выходной файл в первой строке вывести целое число `N` – минимальное количество действий над кубиком, приводящее к решению головоломки. Далее должны быть выведены `N` строк с этими действиями, каждое действие на отдельной строке. Любой минимальный вариант решения может быть выведен.
Пример ввода
BWWBBWWB
Пример вывода
2 RU RU
