Teleport Out!#540
You are in a rectangular maze and want to leave as quickly as possible. The maze is a grid of square locations. Some locations are blocked, while others are exits. If you reach an exit, you can immediately leave the maze.
You may move one step at a time to an adjacent location. Two locations are adjacent if they share a side. Thus, you may move one step north, south, east, or west. You cannot step outside the maze or onto a blocked location.
At any step, you may choose to use your teleport device. This device sends you to a random non-blocked location in the maze, chosen uniformly at random (possibly the location you are already on). If you are teleported onto an exit, you leave the maze immediately.
The only way to leave the maze is to move onto an exit, either by walking or teleporting. You cannot leave by stepping outside the maze. Write a program to calculate the expected minimum number of steps needed to leave the maze, assuming you make optimal choices (moves and when to teleport) to minimize this value. Using the teleport device counts as one step.
There are multiple test cases. Each test case starts with a line containing two positive integers and (R \leq 200, C \leq 200). The next lines each contain characters, representing the maze. Each character is one of:
E: an exit. Each maze has at least one E.
Y: your starting position. Each maze has exactly one Y.
X: a blocked location.
.: an empty location.
You may move or teleport onto any location marked E, Y, or ..
Input ends with a line containing two space-separated 0.
For each test case, print a single line with the minimum expected number of steps to leave the maze, assuming optimal choices, with 3 decimal places. Print no blank lines between outputs.
Example 1