spoj#AVMG2. Another Valentine Maze Game (2D)
Another Valentine Maze Game (2D)
Happy Valentine Day!
Picture Source: http://www.printactivities.com/Mazes/Shape_Mazes/Heart_Maze.html
In this valentine day, I'm very happy to know that many SPOJ user happy to help me on my old Valentine Maze Game (2 years ago). I can't imagine what happen if no one guide me in the maze to meet her (my love), of course it will be much worse, because I can lost in the maze for long time. Now, can you help me again to compute what is expected time needed to meet her in the maze if I just walk uniform randomly on all possible dirrection without any guide? I will be very grateful for your help.
For simplicity, there will be no Chocolate in the map, of course I have collected all the chocolates this valentine 
.
Given a map size m×n, containing 4 possible elements:
'.' denoting road (I can walk on this area)
'#' denoting wall (I can't walk on this area)
'T' denoting my position (Tjandra) at start (time 0), only appear once on the map.
'W' denoting Woman I want to meet (Destination), only appear once on the map.
Tjandra always walk one valid step left, right, up or down for each unit of time with equal probability on which direction. Valid step means I still inside the maze and not walk to the wall, I never stop until I arrive on my destination.
Input
On the first line, there is an integer t denoting number of test cases. Number of test case will be less than or equal to 250.
For each test case:
the first one there are two integers m and n denoting size of map. m and n will be less than or equal to 50.
Next m line(s) there are n characters, each character is element of map that has been described above.
Output
For each test case, output expected time required for me to meet her if I just walk uniform randomly on all possible dirrection. Your answer are considered correct if absolute error with judge (my) solution is less than 10-5. It's guaranteed that my solution has absolute difference less than 10-19 with exact answer. If it's impossible for me to reach destination, output "Mission Failed!" without quotes.
Example
Input:
8
1 3
T.W
1 3
.TW
1 4
.T.W
3 3
T..
.#.
..W
3 3
T.#
...
#.W
3 3
T.#
.#.
#.W
3 3
T..
...
..W
5 5
##T##
.#.#.
.....
.#.#.
##W##
Output:
4.000000000000
3.000000000000
8.000000000000
16.000000000000
16.000000000000
Mission Failed!
18.000000000000
48.000000000000
Explanation
On first test case at time 0, I have one choice: walk right, at time 1 the map will be ".TW" I have two choice , walk right or left with equal probability 0.5 vs 0.5. If I walk right then my mission is completed, so there are 0.5 (50%) chance that I completed my mission at time 2. If I walk left, at time 2 the map will be back to first "T.W" I have one choice again (walk right), at time 3 the map will be ".TW" I have two choice again with equal probability. If I walk right then my mission is completed, so there are 0.5*0.5=0.25 (25%) chance that I completed my mission at time 4. By continuing, we get the series:
2 step with (1/2) chance
4 step with (1/4) chance
6 step with (1/8) chance
...
the answer (expected time) will be 2*1/2+4*1/4+6*1/8+8*1/16+... this series will converge to 4.
On second test case, initial map is equal to first case at time 1, so the expected time will be 1 unit less than first case. The expected time = 4 - 1 = 3.
Time Limit ≈ 2.5*(My Program Speed, without applying any optimization trick)