SP22741 AVMG2 - Another Valentine Maze Game (2D)

**Happy Valentine Day!**  Picture Source: [http://www.printactivities.com/Mazes/Shape\_Mazes/Heart\_Maze.html](http://www.printactivities.com/Mazes/Shape_Mazes/Heart_Maze.html "VMaze Source") 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.

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.

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.