472. Sokoban

Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Sokoban (warehouse keeper) is a transport puzzle in which the player pushes boxes around a maze, viewed from above, and tries to put them in designated locations. Only one box may be pushed at a time, and boxes cannot be pulled. The problem of solving Sokoban puzzles has been proven to be NP-hard.

From Wikipedia, the free encyclopedia

Probably, everybody at least once in his life played this famous game. And despite the fact the problem is NP-hard you are required to write a program which solves this puzzle for quite huge mazes; moreover, it is needed to find the best solution to the puzzle. Specifically, from all possible solutions you are to select the one with the smallest number of box pushes. From all such solutions you need the one that minimizes the total number of moves. To simplify your task a bit, only puzzles with one box will be given to your program to solve.

Input
Maze for solving is given in the input file, maze has a size up to 100 x 100 cells. Every line of input file represents one row of the maze, all lines have the same length (and equal to the width of the maze). Space character represents a passable cell, where box and sokoban may stay, and "
#
" character represents an impassable wall. "
@
" character represents sokoban itself, "
$
" represents a cell in which the box is initially located, and "
.
" represents a cell where sokoban should put the box. Cells in which sokoban, box and destination cell are initially located are passable. Input file will contain every of the characters "
@
", "
$
" and "
.
" exactly once. Maze will be closed in a sense that sokoban will be unable to leave it.

Output
If there is no solution for the given maze, write to the output file the only message "
Impossible.
". Otherwise write one of the best (in the abovementioned sense) solutions. Each move is represented by one of the four characters: "
u
" means moving up, "
r
" — right, "
d
" — down and "
l
" — left. Use capital letters (i.e. "
U
", "
R
", "
D
" and "
L
") to represent moves when sokoban pushes the box.

Example(s)
sample input
sample output
#### 
#  ##
#@$ #
#.# #
#   #
#####
ddrruuLulD

sample input
sample output
#### 
#  ##
#@$ #
#.# #
# # #
#####
Impossible.




Online Contester Team © 2002 - 2010. All rights reserved.