<ПРЕД Задача:
СЛЕД>
Задачу решили 9 пользователей: strider, fetetriste, defrager, Dest, Zhukov_Dmitry, RAVEman, vi002, avg79, tema.dudko_211.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Микро Сокобан

Time limit = 5 секунд(ы)

Memory limit = 65536 Kb

Вам предлагается написать программу-решатель для популярной игры "Микро Сокобан".

Суть игры такова. Вам дан вид сверху на двумерное игровое поле, символизирующее помещение, в котором находится несколько ящиков и человечек — грузчик. Поле разбито на квадратные клетки, в которых может находится ящик, человечек либо непроходимый блок стены. Некоторые свободные от стен клетки помечены как "целевые", количество которых равно количеству ящиков и на которые эти ящики нужно передвинуть — это и есть цель игры. Грузчик за один ход может либо перейти на одну из четырёх соседних клеток, если там нет стены или ящика, либо подвинуть на одну клетку один ящик, если этому не препятствует стена или другой ящик. Грузчик может только толкать ящики, но не тянуть. Ваша задача — по данному начальному расположению найти последовательность ходов, приводящую к решению головоломки.

Вход В первой строке через пробел записаны два числа H и W — высота и ширина игрового прямоугольного поля, 3 ≤ H, W ≤ 10. Далее идут H строк, по W символов каждая. Для обозначения различных состояний клеток используются следующие символы:

Известно, что окаймляющие ячейки игрового поля — всегда стены. Известно, что исходное расположение ящиков не является решением.

Выход Выведите строку, описывающую последовательность ходов. Строка должна содержать только символы 'u', 'd', 'r', 'l', означающие перемещение грузчика соответственно вверх, вниз, вправо и влево, и символы 'U', 'D', 'R', 'L', если при перемещении в соответствующем направлении двигается ящик. Вы должны уложиться в 2000 ходов.

Вход#1
6 6
######
#@  ##
#.$* #
#  # #
#    #
######
Выход#1
rDlddrrruuLLulDrrrddllUdrruululldRddlU

Автор:
Игра Сокобан - Хироюки Имабаяси, 1980 г. Условия и тесты для El Judge - Алексей Захаренков, 2010 г. Большинство уровней взято из программы Micro Sokoban(c) автора Alex Artamonov 2000
30 марта 2010 г.

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 3.235.137.159