A6628. 「SDOI2011」迷宫探险
编程题
省选/NOI-
知识点
题目描述
这是一个单人游戏。
游戏开始时，玩家控制的人物出生在迷宫的某个位置，玩家的目标是控制人物走到迷宫的某个出口（出口可能有多个）。
迷宫里有 $K$ 类陷阱（用
同一类陷阱的状态相同，即用同一个字母标志的陷阱要么全部有害，要么全部无害，不会发生一部分有害而另一部分无害的情况。任何陷阱状态的组合都有一个发生概率，考虑下例：
当 $K = 2$ 时，迷宫内共有两类陷阱，分别用
-
-
-
-
下列表格是一个合法的概率表格：
| |
|:-------:|:-----------:|:-----------:|
| **
| **
当 $K=3$ 时，会有 $8$ 种不同的陷阱状态组合，如果我们依然坚持使用概率表格，那么这个表格将会是三维的（$2\times 2 \times 2$，每一维对应着一类陷阱）。当 $K\ge 3$ 时，这将使得题目难以描述。因此我们使用一个大小为 $2^{K}$ 的数组 $p$ 来描述每种情况发生的可能性，$p$ 的下标范围为 $0\sim 2^{K}-1$。
$p$ 是这样生成的：
对于每个可能的陷阱状态组合，考虑所有 $K$ 类陷阱，令 $1$ 表示某个陷阱有害，$0$ 表示某个陷阱无害，把
设 $S = \displaystyle\sum_{i=0}^{2^K-1} p_i$，则陷阱状态组合 $i$ 出现的概率为 $\dfrac {p_{i}} {S}$。
上述表格对应的一个合法数组 $p$ 为 $36,24,24,16$。
当然同一个概率表格可能会对应多个数组 $p$（事实上有无数个数组 $p$ 能够迎合表格数据），例如上述表格同时也对应着下面的数组 $p$：$72,48,48,32$。
玩家控制的人物初始情况下有 $H$ 点生命，当人物踏上某个陷阱时，如果这个陷阱是有害的，那么会损失 $1$ 点生命，否则这个陷阱是无害的，不损失生命。无论上述哪种情况发生，玩家会立刻得到这个陷阱的信息（有害或无害）。一旦生命小于等于 $0$，玩家控制的人物会立刻死亡。
迷宫可以看作 $m\times n$ 的方格地图，每个元素可能是：
-
-
-
-
-
人物可以向上下左右四个方向行走，不可以走对角线，也不可以走出地图。
给定 $m \times n$ 的地图、$K$、$h$ 以及大小为 $2^{K}$ 的概率数组。你的任务是求出在执行最优策略时，人物能活着走出迷宫的概率。
游戏开始时，玩家控制的人物出生在迷宫的某个位置，玩家的目标是控制人物走到迷宫的某个出口（出口可能有多个）。
迷宫里有 $K$ 类陷阱（用
A,B,C ……表示，相同字母代表相同类型的陷阱），每类陷阱可能是有害的或无害的，而在游戏开始时玩家并不知道哪些陷阱是有害的，哪些是无害的。同一类陷阱的状态相同，即用同一个字母标志的陷阱要么全部有害，要么全部无害，不会发生一部分有害而另一部分无害的情况。任何陷阱状态的组合都有一个发生概率，考虑下例：
当 $K = 2$ 时，迷宫内共有两类陷阱，分别用
A 和 B 表示，陷阱状态的组合共有 $4$ 种：-
A 是无害陷阱，B 是无害陷阱。-
A 是有害陷阱，B 是无害陷阱；-
A 是无害陷阱，B 是有害陷阱；-
A 是有害陷阱，B 是有害陷阱；下列表格是一个合法的概率表格：
| |
A 是无害陷阱 | A 是有害陷阱 ||:-------:|:-----------:|:-----------:|
| **
B 是无害陷阱** | $36\%$ | $24\%$ || **
B 是有害陷阱** | $24\%$ | $16\%$ |当 $K=3$ 时，会有 $8$ 种不同的陷阱状态组合，如果我们依然坚持使用概率表格，那么这个表格将会是三维的（$2\times 2 \times 2$，每一维对应着一类陷阱）。当 $K\ge 3$ 时，这将使得题目难以描述。因此我们使用一个大小为 $2^{K}$ 的数组 $p$ 来描述每种情况发生的可能性，$p$ 的下标范围为 $0\sim 2^{K}-1$。
$p$ 是这样生成的：
对于每个可能的陷阱状态组合，考虑所有 $K$ 类陷阱，令 $1$ 表示某个陷阱有害，$0$ 表示某个陷阱无害，把
A 作为二进制数的第 $0$ 位（从右边开始计数），B 作为第 $1$ 位，C 作为第 $2$ 位……通过以上操作，我们可以得到一个 $K$ 位的二进制数，把它转化成十进制后，$2^{K}$ 种陷阱状态的组合将会与整数 $0\sim2^{K}-1$ 一一对应。设 $S = \displaystyle\sum_{i=0}^{2^K-1} p_i$，则陷阱状态组合 $i$ 出现的概率为 $\dfrac {p_{i}} {S}$。
上述表格对应的一个合法数组 $p$ 为 $36,24,24,16$。
当然同一个概率表格可能会对应多个数组 $p$（事实上有无数个数组 $p$ 能够迎合表格数据），例如上述表格同时也对应着下面的数组 $p$：$72,48,48,32$。
玩家控制的人物初始情况下有 $H$ 点生命，当人物踏上某个陷阱时，如果这个陷阱是有害的，那么会损失 $1$ 点生命，否则这个陷阱是无害的，不损失生命。无论上述哪种情况发生，玩家会立刻得到这个陷阱的信息（有害或无害）。一旦生命小于等于 $0$，玩家控制的人物会立刻死亡。
迷宫可以看作 $m\times n$ 的方格地图，每个元素可能是：
-
.：表示这是平地，可以通过；-
#：表示这是墙，不能通过；-
A，B ，C……：表示这是一个陷阱；-
$：表示这是起点，地图中有且仅有一个；-
@：表示这是终点，地图中可以有多个，也可以一个也没有。人物可以向上下左右四个方向行走，不可以走对角线，也不可以走出地图。
给定 $m \times n$ 的地图、$K$、$h$ 以及大小为 $2^{K}$ 的概率数组。你的任务是求出在执行最优策略时，人物能活着走出迷宫的概率。
输入格式
第一行包含 $4$ 个整数，分别表示 $m,n,K,H$；
下面 $m$ 行每行 $n$ 个字符描述迷宫地图；
最后一行包含 $2^K$ 个非负整数描述数组 $p$，数组下标从 $0$ 开始。
下面 $m$ 行每行 $n$ 个字符描述迷宫地图；
最后一行包含 $2^K$ 个非负整数描述数组 $p$，数组下标从 $0$ 开始。
输出格式
仅包含一个数字，表示在执行最优策略时，人物活着走出迷宫的概率。四舍五入保留 $3$ 位小数。
输入输出样例
输入 #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
说明/提示
| 测试点编号 | $m$ | $n$ | $K$ | $H$ |
|:--------:|:---:|:----:|:---:|:---:|
| $1$ | $29$ | $28$ | $5$ | $1$ |
| $2$ | $28$ | $20$ | $4$ | $1$ |
| $3$ | $25$ | $30$ | $1$ | $1$ |
| $4$ | $25$ | $30$ | $1$ | $2$ |
| $5$ | $25$ | $30$ | $1$ | $3$ |
| $6$ | $5$ | $5$ | $4$ | $4$ |
| $7$ | $12$ | $11$ | $4$ | $5$ |
| $8$ | $19$ | $17$ | $5$ | $3$ |
| $9$ | $23$ | $25$ | $5$ | $4$ |
| $10$ | $30$ | $29$ | $5$ | $5$ |
对于 $100\%$ 的数据，$0 \leq p_i \leq 10^5$，且至少有一个 $p_i \gt 0$ 。
|:--------:|:---:|:----:|:---:|:---:|
| $1$ | $29$ | $28$ | $5$ | $1$ |
| $2$ | $28$ | $20$ | $4$ | $1$ |
| $3$ | $25$ | $30$ | $1$ | $1$ |
| $4$ | $25$ | $30$ | $1$ | $2$ |
| $5$ | $25$ | $30$ | $1$ | $3$ |
| $6$ | $5$ | $5$ | $4$ | $4$ |
| $7$ | $12$ | $11$ | $4$ | $5$ |
| $8$ | $19$ | $17$ | $5$ | $3$ |
| $9$ | $23$ | $25$ | $5$ | $4$ |
| $10$ | $30$ | $29$ | $5$ | $5$ |
对于 $100\%$ 的数据，$0 \leq p_i \leq 10^5$，且至少有一个 $p_i \gt 0$ 。