Teleport Out!

You are inside a rectangular maze and want to leave it in as few steps as possible. The maze is a grid of square cells. Some cells are blocked, and some cells are exits; the instant you reach an exit cell you leave the maze immediately.

On each step you may choose one of the following:

• Walk. Move onto one of the four cells directly adjacent (north, south, east, or west) to your current cell. You may not step outside the maze and you may not step onto a blocked cell.
• Teleport. The teleport device sends you to a cell chosen uniformly at random among all non-blocked cells of the maze, including the cell you are currently standing on. If it places you on an exit, you leave immediately.

Walking one cell counts as one step, and using the teleport device also counts as one step. The only way to leave the maze is to reach an exit (by walking or by teleporting); you can never step off the boundary.

You act optimally so as to minimize the expected number of steps needed to leave. Compute that minimum expected number of steps.

The input contains several test cases. Each test case begins with a line holding two positive integers $R$ and $C$ ($R \le 200$, $C \le 200$), the number of rows and columns. Each of the next $R$ lines contains exactly $C$ characters describing one row of the maze, where each character is one of:

• E — an exit. Every maze contains at least one E.
• Y — your starting cell. Every maze contains exactly one Y.
• X — a blocked cell.
• . — an empty cell.

You may walk or teleport onto any cell marked E, Y, or .. The input ends with a line containing two zeros separated by a space.

For each test case, print a single line with the minimum expected number of steps required to leave the maze when you choose your moves optimally. Print the value rounded to exactly three digits after the decimal point. Do not print blank lines between the answers.