NBLINDESC  Not So Blind Escape
Assume that the maze is laid out on a N x M grid, and each grid location is either blocked or free. Illidan starts from a free location at time 0, and his goal is to escape from the maze. He has four possible moves  move to North, East, South or West. Making a move to an adjacent cell takes exactly 1 unit of time. If Illidan attempts to move out of the grid or attempts to move into an obstacle, he will stay in his current location but it will still cost him 1 unit of time. There is exactly one exit in the maze, located in one of the free cells. Illidan escapes immediately whenever he reaches the exit.
Keep in mind that Illidan is blind, so he may get confused while making a move. To avoid all this chaos, he decided to follow a rather simple strategy. Before he starts his journey to escape the maze, he selects four real numbers: P_{N}, P_{E}, P_{S} and P_{W} denoting the probability to move North, East, South and West respectively. No matter where he is, he will always attempt to move North with probability P_{N}, East with probability P_{E}, South with probability P_{S}, and West with probability P_{W}. At any moment, Illidan must attempt to make a move in one of these four directions. In other words, this means that P_{N} + P_{E} + P_{S} + P_{W} = 1 must be equal to 1.
Illidan does not want to be stuck in the maze for too long. He has information about the maze so he knows his starting position, the location of the exit cell and all the free cells and obstacles initially. Before he attempts to escape, he would like to set the values P_{N}, P_{E}, P_{S} and P_{W} such that the expected time for him to escape the maze is minimized.
Given the description of the maze, Illidan’s starting position and the location of the exit cell, calculate the minimum expected time for Illidan to escape. You can safely assume that Ilidan’s starting cell and the exit cell will always be connected, that is, it will be possible to reach the exit cell via some sequence of moves.
Input
The first line of the input contains an integer T, denoting the number of test cases. Then the description of T test cases follow. The first line of every test case will start with a blank line. The second line contains two space separated integers, N and M denoting the number of rows and the number of columns of the grid. Each of the next N lines will contain exactly M characters on each line describing the grid. The grid will only consist of the characters . @ # and *.. indicates a free cell.
@ indicates Illidan’s starting position which is also a free cell and will occur exactly once.
# denotes an obstacle.
* denotes the location of the exit cell, is of course a free cell and will occur exactly once.
Constraints
Output
For each test case, print the expected time for Illidan to escape the maze if he chooses the probabilities optimally in a single line. Absolute error less than 10^{6} will be ignored.Sample Input
2 1 2 @* 3 3 @.. #.# ..*
Sample Output
1.0000000000000 16.360252929211
Credits
Problem name and story inspired by LightOJ 1426  Blind EscapeOr if you prefer a blinder (easier) version SPOJ BLINDESC  Blind Escape II
hide comments
suhash:
20200619 15:39:22
sgtlaugh@: Could you tell me if my latest submission only has precision errors or is it failing for some cases? [EDIT] nvm: I think I found some issues with my code.


[Rampage] Blue.Mary:
20191118 04:29:44
Is the error bound actually absolute or relative?

Added by:  sgtlaugh 
Date:  20191116 
Time limit:  16s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own Problem, Used in 20192020 ACMICPC Asia Bangkok Regional Contest 