SP22741 AVMG2 - Another Valentine Maze Game (2D)
题目描述
**情人节快乐！**
图片来源：[http://www.printactivities.com/Mazes/Shape\_Mazes/Heart\_Maze.html](http://www.printactivities.com/Mazes/Shape_Mazes/Heart_Maze.html "VMaze Source")
在这个情人节，我非常高兴地知道，很多 SPOJ 用户愿意帮助我玩我两年前的情人节迷宫游戏。如果没有人引导我去见她（我的爱人），我简直无法想象会遇到多大的麻烦，可能还会在迷宫里迷路很长时间。现在，你能再次帮我计算一下，如果我不依赖任何指引，仅在不同方向上随机行走，预计要花多长时间才能见到她呢？你的帮助对我意义重大。
为简化问题，地图上没有巧克力，因为今年情人节我已经把所有巧克力都收集好了! 。
给定一个大小为 **m**×**n** 的地图，地图上有如下 4 种元素：
1. **'.'** 表示可以行走的道路。
2. **'#'** 表示无法通过的墙壁。
3. **'T'** 表示我的起始位置，只会在地图上出现一次。
4. **'W'** 表示我想去见的女人，也仅在地图上出现一次。
我每单位时间都有相等的概率朝上下左右走一步。有效的行走是指我依然在迷宫内，并且没有撞到墙为限。我会一直走，直到到达目的地。
输入格式
第一行是一个整数 **t**，表示测试用例的数量。测试用例的数量不超过 250。
对于每个测试用例：
第一行有两个整数 **m** 和 **n**，表示地图的大小，**m** 和 **n** 均不超过 50。
接下来的 **m** 行中，每行有 **n** 个字符，表示地图上的元素。
输出格式
对于每个测试用例，输出在所有可能方向上随机行走时，需要的预计时间。如果你的答案与裁判的答案的绝对误差小于 10 $ ^{-5} $，则视为正确。保证裁判的结果与准确答案的绝对差小于 10 $ ^{-19} $。如果我无法到达目的地，则输出 "Mission Failed!"。
**本翻译由 AI 自动生成**