Tribblo 程序的终止概率

题目背景

人们设计了一门有些古怪的二维编程语言，并把它命名为 Tribblo。

在这门语言中，程序的执行者是一只生活在字符矩阵中的小生物——Tribble。它会沿着矩阵移动，并根据遇到的路由器改变方向。某些路径能够到达终止装置，另一些路径则会让程序永远无法结束。

给定一段 Tribblo 程序，请计算它最终正常终止的概率。

题目描述

一个 Tribblo 程序由一个 $N\times M$ 的字符矩阵表示。

矩阵中可能出现以下字符：

• S：出生点；
• T：终止装置；
• /：斜杠路由器；
• \：反斜杠路由器；
• W：随机转向装置；
• .：空格子。

矩阵中恰好有一个出生点 S。

程序开始时，会在 S 所在的位置生成一只 Tribble。随后，它会从上、下、左、右四个方向中等概率地选择一个方向，并开始移动。因此，四个初始方向被选中的概率均为：

$$\frac14.$$

Tribble 每次沿当前方向移动到相邻格子。根据到达格子的类型，执行下列操作。

空格子

若到达 .，Tribble 保持当前方向继续移动。

斜杠路由器

若到达 /，Tribble 的移动方向按照下列规则改变：

• 向右 $\rightarrow$ 向上；
• 向上 $\rightarrow$ 向右；
• 向左 $\rightarrow$ 向下；
• 向下 $\rightarrow$ 向左。

也就是说，/ 的作用与一面斜杠形镜子相同。

反斜杠路由器

若到达 \，Tribble 的移动方向按照下列规则改变：

• 向右 $\rightarrow$ 向下；
• 向下 $\rightarrow$ 向右；
• 向左 $\rightarrow$ 向上；
• 向上 $\rightarrow$ 向左。

随机转向装置

若到达 W，Tribble 会随机选择顺时针旋转 $90^\circ$ 或逆时针旋转 $90^\circ$。

两种选择的概率均为：

$$\frac12.$$

每次到达 W 时都要重新独立地进行一次随机选择。

矩阵中至多有 $10$ 个 W。

终止装置

若 Tribble 到达 T，程序立即正常终止。

无法终止的情况

出现以下任意一种情况时，程序会陷入无限循环，视为没有终止：

1. Tribble 移出了矩阵边界；
2. Tribble 再次回到了出生点 S。

请计算程序最终正常终止的概率。

输入格式

第一行包含两个整数 $N,M$，分别表示矩阵的行数和列数。

接下来 $N$ 行，每行包含一个长度为 $M$ 的字符串，描述 Tribblo 程序。

输出格式

输出一个实数，表示程序最终正常终止的概率。

若你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

形式化地，设你的输出为 $x$，标准答案为 $y$。若满足以下任一条件，则答案可以被接受：

$$|x-y|\le 10^{-9},$$

或

$$\frac{|x-y|}{|y|}\le 10^{-9}.$$

当 $y=0$ 时，只使用绝对误差进行判断。

数据范围

对于所有测试数据：

• $1\le N\le 50$；
• $1\le M\le 50$；
• 所有输入行的长度均为 $M$；
• 矩阵只包含字符 S、T、/、\、W 和 .；
• 矩阵中恰好包含一个 S；
• 矩阵中至多包含 $10$ 个 W。

样例 1

输入

3 5
..T..
T.S.T
..T..

输出

1.0

解释

无论 Tribble 最初选择哪个方向，它最终都会到达一个终止装置，因此程序一定终止。

样例 2

输入

3 5
.....
T.S.T
.....

输出

0.5

解释

若 Tribble 最初向左或向右移动，程序会正常终止；若最初向上或向下移动，它会离开矩阵。

四个初始方向等概率，其中两个方向能够终止，因此答案为：

$$\frac24=\frac12.$$

样例 3

输入

3 5
./..T
.\..\
S.../

输出

0.25

解释

只有当 Tribble 最初向右移动时，它才会经过若干路由器后到达终止装置。其他三个初始方向都会使它离开矩阵。

因此终止概率为：

$$\frac14.$$

样例 4

输入

3 7
...W..T
.......
...S...

输出

0.125

解释

Tribble 以 $\frac14$ 的概率最初向上移动并到达 W。

到达 W 后，它有 $\frac12$ 的概率向右转并最终到达 T，另有 $\frac12$ 的概率向左转并离开矩阵。因此：

$$\frac14\times\frac12=\frac18=0.125.$$

样例 5

输入

4 17
..../T....T...T..
/..W.W.....T.....
....W...S.W......
.................

输出

0.25

样例 6

输入

2 4
/..\
S../

输出

0.0

解释

在这组数据中，Tribble 可能在路由器作用下再次回到出生点 S。根据题意，这种情况视为程序进入无限循环，因此不会正常终止。