Given a map, how fast can you get the two keys and then escape?
The map is a 2-dimensional grid of squares, each square is either free or filled with a wall. You can move between adjacent free squares vertically or horizontally, diagonal movement is not allowed. You may not go across walls. You have to get the two keys first and then you can go to the door. Notice that before you get the both keys, you can not pass the door.
Hint: Go to the nearest key first is not always the best choice, see the sample test cases.
The input consists of several maps. Each map begins with a line containing two integer numbers R and C (1 <= R, C <= 1000) 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.
k : The position of the key.
w : The wall.
d : The door.
There are exactly two keys and exactly one door.
There is one blank line after each map. The input is terminated by two zeros in place of the map size.
For each map, print one line containing the sentence "Escape in S steps.", where S is the smallest possible number of step to reach the door. If no way to reach the door, output the string "No solution." instead. One step is defined as a movement between two adjacent squares. Grabbing a key or unlocking a door does not count as a step.