No.659 Wandering Maze
タグ : / 解いたユーザー数 100
作問者 :
nmnmnmnmnmnmnm
/ テスター :
tanzaku
Problem Statement
A-kun has obtained a maze consisting of a grid with $R$ rows and $C$ columns.
The rules for moving through the maze are as follows.
・Each cell of the maze is either a wall or empty.
・From a cell, one move goes in the direction of one of 4 kinds of cells: 1 row up, 1 row down, 1 column left, or 1 column right.
・You can enter an empty cell, but you cannot enter a wall cell.
・When, at any given cell, you can enter cells in, for example, $P$ of the 4 directions, the probability of moving in any one of those directions is $\frac{1}{P}$.
・Only when all 4 directions you could go in have walls is it permitted to stay in place for 1 move.
A-kun wants to arrive at the non-wall goal at row $Gy$, column $Gx$ in exactly $T$ moves, starting from the non-wall start at row $Sy$, column $Sx$.
When A-kun moves with the probabilities above, what is the probability that he arrives at the goal?
Note that on the way to finally arriving at the goal, he may move onto the start or the goal.
Input
$R$ $C$ $T$
$Sy$ $Sx$
$Gy$ $Gx$
$B_0$
$B_1$
$\vdots$
$B_{R-1}$
The maze consists of $R$ rows and $C$ columns. $3 \le R,C \le 10$.
$T$ is the number of moves A-kun makes. $1 \le$ T $\le 100000000 = 10^8$.
The start is at row $Sy$, column $Sx$ (0-indexed). $0 < Sy < {R-1}$. $0 < Sx < {C-1}$.
The goal is at row $Gy$, column $Gx$ (0-indexed). $0 < Gy < {R-1}$. $0 < Gx < {C-1}$.
$B_i$ is a string of length $C$ consisting of '.' and '#'. '.' represents an empty cell and '#' represents a wall.
$B_i$ represents the state of row $i$ (0-indexed) of the maze, and its $j$-th character (0-indexed) represents the state of the cell in column $j$.
The cell at row $Sy$, column $Sx$ and the cell at row $Gy$, column $Gx$ are guaranteed to be empty.
All cells in row 0, row $R-1$, column 0, and column $C-1$ are guaranteed to be walls.
Output
Output on one line the probability that A-kun is at the goal after $T$ moves.
Your output is accepted if its absolute error or relative error from the correct answer is at most $10^{-6}$.
Don't forget the newline at the end.
Sample
Sample 1
Input
6 6 5 2 1 4 4 ###### ###.## #....# ###.## ##...# ######
Output
0.0208333333333333
He can arrive with the moves 1 column right, 1 column right, 1 row down, 1 row down, 1 row right.
The probability in that case is $\frac{1}{48}$.
Sample 2
Input
10 9 123 2 5 1 1 ######### #..#....# #..#....# #..#....# #..#....# #..#....# #.......# #..#....# #..#....# #########
Output
0.0143125825613343
Sample 3
Input
3 5 100000000 1 2 1 1 ##### #...# #####
Output
0.0000000000000000
Starting from the cell at row 1, column 2, he cannot finish at the goal cell at row 1, column 1 with an even number of moves.
Sample 4
Input
3 3 100000000 1 1 1 1 ### #.# ###
Output
1.0000000000000000
The start and the goal may be the same.
Also, it is possible to be unable to ever move from the same cell.
Sample 5
Input
9 8 100000000 2 1 5 1 ######## ##.....# #..###.# ###....# ##..#### #.##...# #.#..#.# #...##.# ########
Output
0.0000000000000000
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。