题目描述

Eli 被困在一个有 $N$ 行 $M$ 列的迷宫中。起点是左上角单元格，终点是右下角单元格。为了到达出口，Eli 只会使用向下和向右两种移动。

迷宫中的每个格子都是一座“桥”，桥有三种类型：

• 水平桥 -
• 竖直桥 |
• 十字路口 +

移动规则如下：

• 从水平桥上，只能移动到同一行中相邻的水平桥或十字路口；
• 从竖直桥上，只能移动到同一列中相邻的竖直桥或十字路口；
• 从十字路口上，可以移动到：
  • 下方的竖直桥；
  • 右侧的水平桥；
  • 或下方、右侧的十字路口。

每过 1 分钟，每一座桥（包括 Eli 当前所在的桥）都会以 $50\%$ 的概率旋转 $90^\circ$：

• - 以 $\frac12$ 的概率变成 |，以 $\frac12$ 的概率保持 -；
• | 以 $\frac12$ 的概率变成 -，以 $\frac12$ 的概率保持 |；
• + 无论如何都保持 +。

Eli 从一个格子移动到相邻格子需要 1 分钟。从第 1 分钟开始，每分钟她会：

• 向下走；
• 或向右走；
• 如果两个方向都不能走，就停在原地；
• 如果两个方向都能走，就等概率随机选择其中一个方向。

Eli 不能走出迷宫边界。

每一分钟中的事件顺序为：

1. 先有一些桥旋转（可能全部旋转，也可能一个都不旋转）；
2. 然后 Eli 决定往哪走，并进行移动（如果有路可走）。

请编写程序 rotmaze，求 Eli 到达右下角格子的期望分钟数。

输入格式

第一行输入两个整数 $N,M$，分别表示迷宫的行数和列数。

接下来输入 $N$ 行，每行一个长度为 $M$ 的字符串，仅由字符 -、|、+ 组成，表示迷宫初始状态。

输出格式

输出一行，一个实数，表示到达终点格子的期望时间，要求恰好保留小数点后 6 位。

数据范围

• $1 \le N,M \le 1000$，且 $\max(N,M)\ge 2$；
• 在 $30\%$ 的测试中，$1 \le N,M \le 3$；
• 在 $60\%$ 的测试中，$1 \le N,M \le 50$。

样例

输入 1

1 3
-+|

输出 1

4.000000

输入 2

2 3
-+|
++-

输出 2

4.250000

输入 3

13 11
-+-+||-+++-
++|+-|--|++
+--+-|-++++
||+-+-||++|
+-+-+||--+-
+--||-|+-|-
|+++++-+-+-
||-||--+||-
|+|-+-+|-|-
+-+++|--||+
+|||--+||-+
+|++|+||+-|
++-+-+|--||

输出 3

36.347956

样例说明

在样例 1 中：

• 第 1 分钟时，若格子 $(1,1)$ 上的桥没有旋转，则 Eli 以概率 $\frac12$ 进入格子 $(1,2)$；
• 若它旋转成 |，则 Eli 必须等待，直到它再次变成 -。

可以证明，Eli 从当前格子走到相邻格子的期望等待时间为：

$$\frac12\cdot1+\frac14\cdot2+\frac18\cdot3+\frac1{16}\cdot4+\cdots=2$$

到达格子 $(1,2)$ 后会遇到同样的问题，因此总期望时间为 $2+2=4$ 分钟。

在样例 2 中，Eli 还可以向下移动。

• 若第 1 分钟格子 $(1,1)$ 旋转成 |，她会在 1 分钟后到达 $(2,1)$，再花 1 分钟到 $(2,2)$，最后期望再花 2 分钟到 $(2,3)$，总期望为 4 分钟；
• 若格子 $(1,1)$ 没有旋转，则 Eli 第 1 分钟到达 $(1,2)$。

接下来：

• 以概率 $\frac12$，格子 $(1,3)$ 会朝向她（即变成 -），此时她会在“向右”和“向下”之间随机选择；
• 否则她会向下走到 $(2,2)$。

因此在第 2 分钟后，Eli 有 $\frac14$ 的概率到达 $(1,3)$，有 $\frac34$ 的概率到达 $(2,2)$。

若位于 $(1,3)$，她需要等待直到 $(1,3)$ 与 $(2,3)$ 两座桥同时变成 |。该等待时间的期望为：

$$\frac14\cdot1+\frac3{16}\cdot2+\frac9{64}\cdot3+\cdots=4$$

所以若经过 $(1,3)$，总耗时期望为 $1+1+4=6$ 分钟。

若位于 $(2,2)$，则只需等待格子 $(2,3)$ 的桥转向她。由样例 1 的分析，该期望为 2 分钟，所以总耗时期望为 $1+1+2=4$ 分钟。

因此，从 $(1,2)$ 出发的期望耗时为：

$$\frac34\cdot4+\frac14\cdot6=4.5$$

整个迷宫的总期望耗时即为：

$$\frac12\cdot4+\frac12\cdot4.5=4.25$$

说明

原题对“期望值”的注释如下：

期望值指在无限次重复实验中结果的平均值。
在本题中，可以想象 Eli 从初始状态下的迷宫出发很多很多次，每次记录她到达出口所花费的分钟数；这些数的平均值就是所求的期望分钟数。