<PREV Problem:
Solved by 9 users: strider, fetetriste, defrager, Dest, Zhukov_Dmitry, RAVEman, vi002, avg79, tema.dudko_211.
RAVEman03 jun 2010C++1401.09562 
RAVEman03 jun 2010C++1201.08762 
vi00210 dec 2010Java2101.711178 
fetetriste29 nov 2010Java1003.021398 
fetetriste31 mar 2010Java802.541516 
defrager04 apr 2010C++2704.761873 
avg7918 dec 2011C++2401.392443 
avg7918 dec 2011C++2301.382488 
avg7919 dec 2011C++2701.382600 
avg7919 dec 2011C++2801.372632 
avg7921 dec 2011C++3601.352674 
strider30 mar 2010C++200.323410 
Dest05 apr 2010C++2100.083631 
tema.dudko_21110 dec 2012C++1000.303831 
tema.dudko_21112 dec 2012C++1100.274029 
Zhukov_Dmitry27 apr 2010C++3900.134560 

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 180ms

SW soft NIX
ID =