<PREV Problem:
Solved by 9 users: strider, fetetriste, defrager, Dest, Zhukov_Dmitry, RAVEman, vi002, avg79, tema.dudko_211.

Micro Sokoban

Time limit = 5 second(s)

Memory limit = 65536 Kb

You are suggested to write a solver program for the popular game 'Micro Sokoban'.

The essence of the game is as follows. You are given a plan view of a 2-dimensional playing field, that is a room where there are some boxes and a man — loader. The field is divided into square cells, each of which can contain a box, a man or an impassable piece of wall. Some wall-free cells are marked as targets, their amount being equal the number of boxes.

The game aim is to place all boxes on the target cells. During a move the loader can go to one of the four neighbouring cells if there is no a box or a wall there, or push only one box for one-cell distance, if no other boxes or walls prevent from this. The loader can only push boxes but not pull them. Given the initial disposition, find the moves sequence leading you to the solution of the puzzle.

Input In the first line there are two space-separated integers H and W — the height and the width of the playing field, 3 ≤ H, W ≤ 10. The following H lines contain W characters each. To distinguish among different states of a cell the following characters are used:

It is known that the perimeter of the field is always constructed from walls. It is known that there is something to do.

Output Output a single line describing the move sequence. The line must contain only the symbols 'u', 'd', 'r', 'l' indicating the loader's movement up, down, left or right, correspondingly, and the symbols 'U', 'D', 'R', 'L' if the move is accompanied by the shift of a box. You are allowed to make no more than 2000 moves.

6 6
#@  ##
#.$* #
#  # #
#    #

Sokoban game - Hiroyuki Imabayashi, 1980. Сondition and tests for El Judge - Alexey Zakharenkov, 2010. The most of levels were taken from 'Micro Sokoban' program (c) by Alex Artamonov 2000
march 30, 2010

<PREV | Problem set | Search related messages | NEXT>

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

SW soft NIX
ID =