SP22740 AVMG1 - Another Valentine Maze Game (1D)

**情人节快乐！**  图片来源：[http://www.printactivities.com/Mazes/Shape\_Mazes/Heart\_Maze.html](http://www.printactivities.com/Mazes/Shape_Mazes/Heart_Maze.html "VMaze Source") 在这个情人节，我很高兴地知道很多 SPOJ 用户愿意帮助我完成两年前的情人节迷宫游戏。如果没有人的指引，我或许会在迷宫中迷路而无法与她（我的爱人）见面。现在，请你再次帮我计算：在缺乏导引的情况下，若我在所有可能的方向上随机行走，预计需要多少时间才能在迷宫中地与她相遇？对你的帮助，我将不胜感激。 为简单起见，本题中不考虑巧克力和墙壁，而且迷宫是一维的。 有一个长度为 **l** 的地图，包含以下三种字符： - **'.'**：道路，表示我可以行走的区域； - **'T'**：起点，我的位置（Tjandra），在地图上仅出现一次； - **'W'**：目的地，我想见的对象（女人），在地图上也仅出现一次。 Tjandra 每个单位时间都会向左或向右走一步（前提是步移动后仍在迷宫内），两种方向的概率相等。我将持续行走，直到到达目的地。

第一行输入一个整数 **t**，表示测试用例的数量。测试用例的数量不超过 250。 对于每个测试用例，输入两行。第一行是一个整数 **l**，表示地图的长度，长度不超过 50。第二行是 **l** 个字符，代表上述描述的地图元素之一。

对于每个测试用例，输出我在随机行走下与她相遇的期望时间。只要你的答案与标准答案的绝对误差小于 10 $ ^{-5} $，就视为正确。保证我的解决方案与精确答案的绝对误差小于 10 $ ^{-19} $。

- $1 \le t \le 250$ - $1 \le l \le 50$ **本翻译由 AI 自动生成**