問題一覧 > 通常問題

No.659 徘徊迷路

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 98
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm / テスター : tanzakutanzaku
6 ProblemId : 1570 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-03-02 18:10:19

問題文

A君は$R$行$C$列のマスからなる迷路を手に入れました。
迷路を移動するルールは次のようなものです。

・迷路上の1つのマスは壁か空白のいずれかです。
・あるマスにいるとき1回で1行上、1行下、1列左、1列右の4種類のいずれかのマスの方向へ進めます。
・空白のマスに入ることはできますが、壁のマスには入ることができません。
・任意のマスで例えば4種類の方向のうち$P$種類のマスに入ることができるとき、その1種類の方向に移動する確率は$\frac{1}{P}$です。
・進むことができる4種類の方向にすべて壁がある場合のみ1回の移動でその場から移動しないことが許されます。

A君は壁でないスタート地点$Sy$行$Sx$列からちょうど$T$回の移動で壁でないゴール地点$Gy$行$Gx$列に到着したい。
A君が上記の確率で移動するときゴール地点に到着する確率はどれだけか?
なお、最終的にゴール地点に到着する途中でスタート地点、ゴール地点に移動しても良い。

入力

$R$ $C$ $T$
$Sy$ $Sx$
$Gy$ $Gx$
$B_0$
$B_1$
$\vdots$
$B_{R-1}$

迷路は$R$行$C$列からなる。$3 \le R,C \le 10$。
$T$はA君が移動する回数。$1 \le$ T $\le 100000000 = 10^8$。
スタート地点は$Sy$行$Sx$列(0-index)。$0 < Sy < {R-1}$。$0 < Sx < {C-1}$。
ゴール地点は$Gy$行$Gx$列(0-index)。$0 < Gy < {R-1}$。$0 < Gx < {C-1}$。
$B_i$は'.'か'#'からなる文字数が$C$の文字列。'.'は空白、'#'は壁をあらわす。
$B_i$は$i$行目(0-index)の迷路の状態を表しその$j$文字目(0-index)は$j$列のマスの状態をあらわす.
$Sy$行$Sx$列と$Gy$行$Gx$列はかならず空白である。
0行、$R-1$行、0列、$C-1$列のすべてのマスはかならず壁である。

出力

A君が$T$回の移動後にゴール地点にいる確率を1行で出力せよ。
ただし、正解と出力の許容誤差は絶対誤差または相対誤差が$10^{-6}$ 以下とする。
最後に改行を忘れずに。

サンプル

サンプル1
入力
6 6 5
2 1
4 4
######
###.##
#....#
###.##
##...#
######
出力
0.0208333333333333

1列右、1列右、1行下、1行下、1行右の移動で到着できます。
そのときの確率は$\frac{1}{48}$です。

サンプル2
入力
10 9 123
2 5
1 1
#########
#..#....#
#..#....#
#..#....#
#..#....#
#..#....#
#.......#
#..#....#
#..#....#
#########
出力
0.0143125825613343

サンプル3
入力
3 5 100000000
1 2
1 1
#####
#...#
#####
出力
0.0000000000000000

1行2列のマスからスタートすると偶数回の移動で1行1列のマスにゴールはできません。

サンプル4
入力
3 3 100000000
1 1
1 1
###
#.#
###
出力
1.0000000000000000

スタート地点とゴール地点は同じ場合があります。
また、同じ地点からずっと動けないという状況もありえます。

サンプル5
入力
9 8 100000000
2 1
5 1
########
##.....#
#..###.#
###....#
##..####
#.##...#
#.#..#.#
#...##.#
########
出力
0.0000000000000000

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。