Program | SOKO.C, SOKO.CPP, SOKO.PAS |
Imagine you are standing inside a two dimensional maze composed of square cells
which may or may not be filled with rock. You can move east, west, north and
south one cell at a step. These moves are called walks.
One of the empty cells contains a box, which can be moved to adjacent free cell
by standing next to the box and then moving in the direction of the box. Such
a move is called a push. The box cannot be moved in any other way than by pushing,
which means that if you push it into the corner you can never get it out of
the corner again.
One of the empty cells is marked as the target cell. Your job is to bring the
box to the target cell by a sequence of walks and pushes. As the box is heavy,
you would like to minimize the number of pushes. Can you write a program that
will work out the best such sequence?
1 7
SB....T
1 7
SB..#.T
7 11
########### #T##......# #.#.#..#### #....B....# .#######..# #.....S...# ###########
Sample Output
Maze #1
EEEEE
Maze #2
Impossible.
Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN
Maze #4
swwwnnnnnneeesssSSS