Игра в 8
(Время: 2 сек. Память: 64 Мб Сложность: 55%)
В квадратной коробке размером 3×3 находятся 8 фишек, на которых написаны цифры от 1 до 8. Таким образом, в коробке есть одна пустая ячейка, в которую за один ход разрешается перемещать соседнюю фишку. В начале игры фишки перемешаны. Задача игрока состоит в том, чтобы, не вынимая фишки из коробки, выстроить фишки в правильном порядке (см. рисунок).
Ваша задача – решить эту задачу за минимальное число ходов.
Входные данные
Входной файл INPUT.TXT содержит три строки, в каждой из которых записаны три цифры от 0 до 8 через пробел. Цифрой «0» обозначается пустая клетка. Гарантируется, что все цифры различны.
Выходные данные
В выходной файл OUTPUT.TXT выведите решение в виде строки из символов «L», «R», «U» и «D» – последовательность команд по перемещению пустого поля в направлениях «влево», «вправо», «вверх» и «вниз» соответственно. Гарантируется, что решение существует. Если существует несколько правильных решений – выведите любое.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1 2 3
4 5 6
7 0 8 | R |
| 2 | 1 2 3
4 5 6
7 8 0 | |
| 3 | 1 2 3
0 6 8
4 7 5 | DRRULDR |
Пояснение к третьему примеру
Система оценки
Решения, анализирующие не более трёх ходов, будут оцениваться в 10 баллов.
Решения, анализирующие не более шести ходов, будут оцениваться в 20 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
