問題文
有一个由方格组成的迷宫。
迷宫的每个格子可以是巢、方糖、墙或空地,arida 想要从左上角的巢格子到右下角的方糖格子。
包含方糖的格子在内,每个非墙格子都可以到达,且没有循环路径。
此外,(奇数,奇数) 的地点一定是墙,(偶数,偶数) 的地点一定是空地。
这里的坐标将左上角有巢的地点定为 (0,0) ,1 向右的坐标为 (1,0)、1 向下的坐标为 (0,1) 。
这种迷宫的例子如图 1 所示。
黄色绿色部分是 (奇数,奇数) 的地点,橙色部分是 (偶数,偶数) 的地点。
这里的阿里,在可以直行的情况下直行,撞到墙的情况下以 1/2 的正确率向左,1/2 概率向右转向的属性。如果你撞到了一堵墙,而两边都有墙,你总是会向相反的方向转弯。
如果它不能向任一方向转动(如果三个方向都是墙壁或迷宫外),蚂蚁就会当场死亡并变成一堵墙。
巢穴下方有墙,所以一开始只能向右移动。另外,方糖所在的广场左边有一堵墙,所以你只能从上方到达方糖所在的广场。
例如,图
该图显示了 1 的情况
如 2 所示,1 第二只蚂蚁会一直走,所以它会移动到右上角。 (4,0) 你将被墙壁包围并位于迷宫外,并且会死亡。
2 第二只蚂蚁是 (4,0) 是 1 墙是由第二只蚂蚁形成的,所以 1 在...前面 (3,0) 会让你死亡并变成一堵墙。
结果,
在3 匹目、4 第二只蚂蚁是 (2,0) 处右转,
每个人都死于(2,4)、(2,3) 。
5 第二只蚂蚁是 (2,2) 所以你不能直走,
转至(1,2) 这个类型的变量里只能放入 (3,2) 。
如果你朝
(1,2) 方向走
你会死在 (0,4) ,但是
如果你朝(3,2) 方向走,你就会到达方糖。
如果蚂蚁重复此行为直到到达方糖,请找到到达方糖所需的预期蚂蚁数量。
入力
N
c_{(0,0)}c_{(1,0)}‥‥c_{(N-1,0)}
c_{(1,1)}c_{(1,1)}‥‥c_{(N-1,1)}
:
:
c_{(0,N-2)}c_{(1,N-2)}‥‥c_{(N-1,N-2)}
c_{(0,N-1)}c_{(1,N-1)}‥‥c_{(N-1,N-1)}
- 输入是 有一行 N+1 。
- 1 行包含表示给定迷宫的长度和宽度的整数。 N(5≦N≦49) 被给予。
- N 是奇数。 在
- 2 从线 N 行中,每行都包含一个表示图形状的状态。 c_{(i,j)}(0≦i,j≦N-1) 是 N 给出的字符。
- c_{(i,j)} 是以下之一,每个点 (i,j) 表示方块处于以下状态。
S:表示该方格是一个嵌套。G:表示该方格内有一块方糖。#:表示该正方形是一面墙。.:表示该广场为空地。
- c_{(0,0)} 必须是
S。c_{(N-1,N-1)} 必须是G。另外,S和G仅存在于该位置。 S到 1 以下几点 c_{(1,0)} 和G到 1 指向左侧 c_{(N-1,N-2)} 必须是#。- i 和 j 均为奇数的点总是
#。i 和 j 均为偶数的点总是.。
- c_{(i,j)} 是以下之一,每个点 (i,j) 表示方块处于以下状态。
部分点
出力
误差至少是绝对误差和相对误差之一。 1e−6(10^{-6}) 如果低于则允许。 请注意,行尾需要换行。
入力例 1
5 S.... ##.## ..... .#.#. .#.#G
出力例 1
5.937500000
- 每种鱼到达方糖的概率如下。
使用
- 5 达到该目标的概率: 在1/2
- 6 达到该目标的概率:
在1/2×1/2
- (2,2) 的分行 5 第二个是 朝 (1,2) 方向, 当朝6 第二个是 朝 (3,2) 方向转动时
- 7 达到该目标的概率: 在1/2^3
- 8 达到该目标的概率: 在1/2^4
- 9 达到该目标的概率: 在1/2^4×1
- 因此,5×1/2+6×1/2×1/2+7×1/2^3+8×1/2^4+9×1/2^4×1=5.9375 变为。
入力例 2
9 S........ ####.#### ......... .#####.## ...#.#... .#.#.#### .#...#... .#.#.#.#. .#.#...#G
出力例 2
18.029407501
入力例 3
13 S............ ####.#.#.#### .....#.#...#. .###########. .....#.#..... .#.###.###.## .#...#.#..... ##.#.#.#####. .#.#.....#... .#.###.#.#.## ...#...#..... .#.#.#.#.###. .#.#.#.#...#G
出力例 3
35.000000000