C0917 [SDOI2011]迷宫探险

这是一个单人游戏。

游戏开始时，玩家控制的人物出生在迷宫的某个位置，玩家的目标是控制人物走到迷宫的某个出口（出口可能有多个）。迷宫里有k类陷阱（用“A”、“B”、“C”……表示，相同字母代表相同类型的陷阱），每类陷阱可能是有害的或无害的，而在游戏开始时玩家并不知道哪些陷阱是有害的，哪些是无害的。同一类陷阱的状态相同，即用同一个字母标志的陷阱要么全部有害，要么全部无害，不会发生一部分有害而另一部分无害的情况。任何陷阱状态的组合都有一个发生概率，考虑下例：

当 $k=2$ 时，迷宫内共有两类陷阱，分别用“A”和“B”表示，陷阱状态的组合共有 $4$ 种：

1、“A”是无害陷阱，“B”是无害陷阱。

2、“A”是有害陷阱，“B”是无害陷阱；

3、“A”是无害陷阱，“B”是有害陷阱；

4、“A”是有害陷阱，“B”是有害陷阱；

下面给出了一个合法的概率表格：

$\begin{array}{|c|c|c|}\hline & A 是无害陷阱 & A 是有害陷阱 \\\hline B 是无害陷阱 & 36\% & 24\% \\\hline B 是有害陷阱 & 24\% & 16\% \\\hline \end{array}$

当 $K=3$ 时，会有 $8$ 种不同的陷阱状态组合，如果我们依然坚持使用概率表格，那么这个表格将会是三维的（$2 \times 2 \times 2$，每一维对应着一类陷阱）。当 $K≥3$ 时，这将使得题目难以描述。因此我们使用一个大小为 $2k$ 的数组 $p$ 来描述每种情况发生的可能性，$p$ 的下标范围为 $0$~$2k-1$。

$p$ 是这样生成的：

对于每个可能的陷阱状态组合，考虑所有 $k$ 类陷阱，令 $1$ 表示某个陷阱有害，$0$ 表示某个陷阱无害，把“A”作为二进制数的第 $0$ 位（从右边开始计数），“B”作为第 $1$ 位，“C”作为第 $2$ 位……通过以上操作，我们可以得到一个 $K$ 位的二进制数，把它转化成十进制后，$2k$ 种陷阱状态的组合将会与整数 $0$~$2k-1$ 一一对应。

定义 $S$ 表示 $P$ 中所有元素和，即：

则陷阱状态组合 $i$ 出现的概率为 $P_i / S$。上述表格对应的一个合法数组 $P$ 是：

$P_0=36$

$P_1=24$

$P_2=24$

$P_3=16$

当然同一个概率表格可能会对应多个数组 $P$（事实上有无数个数组 $P$ 能够迎合表格数据），例如上述表格同时也对应着下面的数组 $P$：

$P_0=72$

$P_1=48$

$P_2=48$

$P_3=32$

玩家控制的人物初始情况下有 $H$ 点生命，当人物踏上某个陷阱时，如果这个陷阱是有害的，那么会损失 $1$ 点生命，否则这个陷阱是无害的，不损失生命。无论上述哪种情况发生，玩家会立刻得到这个陷阱的信息（有害或无害）。一旦生命小于等于 $0$，玩家控制的人物会立刻死亡。

迷宫可以看作 $m \times n$ 的方格地图，每个元素可能是：

.：表示这是平地，可以通过；

#：表示这是墙，不能通过；

A，B，C……：表示这是一个陷阱；

$：表示这是起点，地图中有且仅有一个；

@：表示这是终点，地图中可以有多个，也可以一个也没有。

人物可以向上下左右四个方向行走，不可以走对角线，也不可以走出地图。

给定 $m \times n$ 的地图、$k$、$h$ 以及大小为 $2k$ 的概率数组。你的任务是求出在执行最优策略时，人物能活着走出迷宫的概率。

样例输入 1

4 3 2 1
.
.
A#B
A#B
.@.
30 30 20 20

样例输出 1

0.600

样例输入 2

4 3 2 2
.$.
A#B
A#B
.@.
30 30 20 20

样例输出 2

0.800

样例输入 3

4 3 2 3
.$.
A#B
A#B
.@.
30 30 20 20

样例输出 3

1.000

样例输入 4

4 3 3 2
.$.
A#B
A#C
@@@
143 37 335 85 95 25 223 57

样例输出 4

0.858