Problem D
Sokoban4

A sokoban map is a two-dimensional grid that contains walls, boxes, goals and one player, as seen in the figure /reffig:ex. The target of the game is to push the boxes onto the goals. Boxes are pushed by walking into them. You cannot pull a box. The position on the other side of the box must be free. You cannot push more than one box at a time. There will always be as many boxes as there are goals. The goals do not need to be clustered in one place.

Figure 1: A graphical illustration of a sokoban map. There is one player, $N$ boxes and goals. In this assignment the task is to push the boxes onto the goals.

Input

Your agent program will get as an input a board as a string where each character represents one cell. Each cell will be one of the following symbols:

’ ’

Free space

’#’

Wall

’.’

Goal

’@’

Sokoban player

’+’

Sokoban player on goal

’$’

Box

’*’

Box on goal

The lines may not have the same length (i.e., there might not be trailing white space). The player will always start inside a region which is enclosed by walls so that s/he cannot escape from the map without crossing a wall.

Output

You should return a string of player movements (composed of a sequence of the characters "U" for up, "D" for down, "L" for left and "R" for right). After the moves are executed, all boxes should stand on one goal each. You may put spaces between the characters but it is optional: "RURU" is equivalent to "R U R U" and "RU R U".

Grading

The grading consists of two parts:

Basic functionality

Your agent is tested on a few simple maps to see if you have the basic functionality in place. If you fail on any of these maps, the whole submission will be rejected. No points are given for these maps.

Scoring

Your agent is tested on 20 maps. Each correct solution gives one point for a total of 20 points. Failing on any of these maps does not lead to your submission being rejected.

We do not require your agent to find the shortest solution for any of the maps.

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

U U R

########
#     .#
#   $$.#
####   #
   #@ ##
   ####

U U R L L U R R

########
#   # .#
#   $$.#
####   #
   #@ ##
   ####

U RR UU L D L DD R U L U R D R U LLL U LL D RRRR