Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Игра в 8

(Время: 2 сек. Память: 64 Мб Сложность: 55%)

В квадратной коробке размером 3×3 находятся 8 фишек, на которых написаны цифры от 1 до 8. Таким образом, в коробке есть одна пустая ячейка, в которую за один ход разрешается перемещать соседнюю фишку. В начале игры фишки перемешаны. Задача игрока состоит в том, чтобы, не вынимая фишки из коробки, выстроить фишки в правильном порядке (см. рисунок).

Ваша задача – решить эту задачу за минимальное число ходов.

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

Входной файл INPUT.TXT содержит три строки, в каждой из которых записаны три цифры от 0 до 8 через пробел. Цифрой «0» обозначается пустая клетка. Гарантируется, что все цифры различны.

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

В выходной файл OUTPUT.TXT выведите решение в виде строки из символов «L», «R», «U» и «D» – последовательность команд по перемещению пустого поля в направлениях «влево», «вправо», «вверх» и «вниз» соответственно. Гарантируется, что решение существует. Если существует несколько правильных решений – выведите любое.

Примеры

INPUT.TXTOUTPUT.TXT
11 2 3
4 5 6
7 0 8
R
21 2 3
4 5 6
7 8 0
31 2 3
0 6 8
4 7 5
DRRULDR

Пояснение к третьему примеру

Система оценки

Решения, анализирующие не более трёх ходов, будут оцениваться в 10 баллов.

Решения, анализирующие не более шести ходов, будут оцениваться в 20 баллов.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 Седьмая командная олимпиада
 A. Винни-Пух
 B. Игра в 8
 C. Треугольник в прямоугольнике
 D. Поход за грибами
 E. Башенки из кубиков
 F. Весёлые качели
 G. Площадь многоугольника
 H. Мирные ладьи

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru