No.659 徘徊迷路
タグ : / 解いたユーザー数 99
作問者 : nmnmnmnmnmnmnm / テスター : tanzaku
問題文
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もしくは右上の雲マークをクリックしてアカウントを作成してください。