← 返回题目列表

AtCoder · tenka1_2012_qualA_4

D. 蚂蚁窝

中文机器翻译题面 查看原题

問題文

有一个由方格组成的迷宫。
迷宫的每个格子可以是巢、方糖、墙或空地,arida 想要从左上角的巢格子到右下角的方糖格子。
包含方糖的格子在内,每个非墙格子都可以到达,且没有循环路径。
此外,(奇数,奇数) 的地点一定是墙,(偶数,偶数) 的地点一定是空地。
这里的坐标将左上角有巢的地点定为 (0,0) ,1 向右的坐标为 (1,0)、1 向下的坐标为 (0,1) 。


这种迷宫的例子如图 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) 方向走,你就会到达方糖。

図 2:図 1 迷宫 1 〜 5 第二只蚂蚁如何移动

如果蚂蚁重复此行为直到到达方糖,请找到到达方糖所需的预期蚂蚁数量。


入力

输入将以以下形式从标准输入给出。
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 均为偶数的点总是 . 。

部分点

迷宫尺寸较小的输入 ( 如果只有5≦N≦9) 是正确的,100 部分积分换满分 50 点。

出力

将蚂蚁到达方糖所在的正方形所需的蚂蚁数量的预期值设置为标准输出。 1 行。
误差至少是绝对误差和相对误差之一。 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