Given a map, how fast can you find the exit and then escape?
The map is a 2-dimensional grid of squares, each square is either free or filled with a wall. The exit is hidden among one of the free spaces.
You can move between adjacent free squares vertically or horizontally, diagonal movement is not allowed. You may not go across walls and leave the range of given map.
You have to arrive the position of button first (so that the exit appears) and then you can go to the exit.
The input consists of several maps. Each map begins with a line containing two integer numbers R and C specifying the map size. Then there are R lines each containing C characters.
Each character is one of the following:
s : Your start position.
. : A free square that you can move.
b : The position of the button.
w : The wall.
e : The hidden exit.
The position of start point, button and exit are guaranteed to be difference.
There are exactly one button and exactly one exit.
There is one blank line after each map. The input is terminated by end of file.
Case 1: 1 <= R, C <= 5
Case 2: 1 <= R, C <= 100
Case 3: 1 <= R, C <= 200
Case 4: 1 <= R, C <= 1000
For each map, print one line containing the sentence "Escape in S steps.", where S is the smallest possible number of step to escape. If no way to escape, output the string "No solution." instead.
One step is defined as a movement between two adjacent squares. Pressing button does not count as a step.