yukicoder-659
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
display: block;
padding: 9.5px;
margin: 0 0 10px;
font-size: 13px;
line-height: 1.42857143;
color: #333;
word-break: break-all;
word-wrap: break-word;
background-color: #f5f5f5;
border: 1px solid #ccc;
border-radius: 4px;
}
</style>
}}}
== [https://yukicoder.me/problems/no/659 No.659 徘徊迷路] ==
=== Description ===
{{{
#!html
<p>给出一个 $R$ 行 $C$ 列的四连通迷宫，'#' 表示墙（不能走），'.' 表示空白（可以走）。起点在 $S_y$ 行 $S_x$ 列，终点在 $G_y$ 行 $G_x$ 列，而且起点终点都是空白格。</p>
<p>如果一个格子和其它 $P$ 个空白格子相邻，那么下一步走到每个相邻空白格子的概率都是 $1/P$，而且每一步必须移动；除非一个格子四面都是墙（没得走），那么下一步一定会呆在这个格子里。求从起点出发，走 $T$ 步恰好到终点的概率。</p>
}}}
=== Input ===
{{{
#!html
<p class="input">
$R$ $C$ $T$<br/>
$S_y$ $S_x$<br/>
$G_y$ $G_x$<br/>
$B_0$<br/>
$B_1$<br/>
$\vdots$<br/>
$B_{R-1}$
</p>
<p>$B_0 \sim B_{R-1}$ 就是迷宫地图，保证最外面一圈都是墙。</p>
<p>$3 \le R, C \le 10$，$1 \le T \le 10^8$。</p>
}}}
=== Output ===
{{{
#!html
<p>输出概率，精确到 $10^{-6}$ 就算正确。</p>
}}}
=== Sample ===
==== Sample 1 ====
输入
{{{
#!html
<pre>
6 6 5
2 1
4 4
######
###.##
#....#
###.##
##...#
######
</pre>
}}}
输出
{{{
#!html
<pre>
0.0208333333333333
</pre>
<p>起点走到终点的最短路恰好 5 步，概率是 $1/48$。</p>
}}}
==== Sample 2 ====
输入
{{{
#!html
<pre>
10 9 123
2 5
1 1
#########
#..#....#
#..#....#
#..#....#
#..#....#
#..#....#
#.......#
#..#....#
#..#....#
#########
</pre>
}}}
输出
{{{
#!html
<pre>
0.0143125825613343
</pre>
}}}
==== Sample 3 ====
输入
{{{
#!html
<pre>
3 5 100000000
1 2
1 1
#####
#...#
#####
</pre>
}}}
输出
{{{
#!html
<pre>
0.0000000000000000
</pre>
<p>只有奇数步才有可能恰好走到终点。</p>
}}}
==== Sample 4 ====
输入
{{{
#!html
<pre>
3 3 100000000
1 1
1 1
###
#.#
###
</pre>
}}}
输出
{{{
#!html
<pre>
1.0000000000000000
</pre>
<p>起点和终点相同，而且起点被墙包围没得走。</p>
}}}
==== Sample 4 ====
输入
{{{
#!html
<pre>
9 8 100000000
2 1
5 1
########
##.....#
#..###.#
###....#
##..####
#.##...#
#.#..#.#
#...##.#
########
</pre>
}}}
输出
{{{
#!html
<pre>
0.0000000000000000
</pre>
<p>起点和终点不连通。</p>
}}}No.659 徘徊迷路
Description
给出一个 $R$ 行 $C$ 列的四连通迷宫，'#' 表示墙（不能走），'.' 表示空白（可以走）。起点在 $S_y$ 行 $S_x$ 列，终点在 $G_y$ 行 $G_x$ 列，而且起点终点都是空白格。
如果一个格子和其它 $P$ 个空白格子相邻，那么下一步走到每个相邻空白格子的概率都是 $1/P$，而且每一步必须移动；除非一个格子四面都是墙（没得走），那么下一步一定会呆在这个格子里。求从起点出发，走 $T$ 步恰好到终点的概率。
Input
$R$ $C$ $T$
$S_y$ $S_x$
$G_y$ $G_x$
$B_0$
$B_1$
$\vdots$
$B_{R-1}$
$B_0 \sim B_{R-1}$ 就是迷宫地图，保证最外面一圈都是墙。
$3 \le R, C \le 10$，$1 \le T \le 10^8$。
Output
输出概率，精确到 $10^{-6}$ 就算正确。
Sample
Sample 1
输入
6 6 52 14 4#########.###....####.####...#######
输出
0.0208333333333333
起点走到终点的最短路恰好 5 步，概率是 $1/48$。
Sample 2
输入
10 9 1232 51 1##########..#....##..#....##..#....##..#....##..#....##.......##..#....##..#....##########
输出
0.0143125825613343
Sample 3
输入
3 5 1000000001 21 1######...######
输出
0.0000000000000000
只有奇数步才有可能恰好走到终点。
Sample 4
输入
3 3 1000000001 11 1####.####
输出
1.0000000000000000
起点和终点相同，而且起点被墙包围没得走。
Sample 4
输入
9 8 1000000002 15 1##########.....##..###.####....###..#####.##...##.#..#.##...##.#########
输出
0.0000000000000000
起点和终点不连通。