#102246. [BZOJ 2246] [SDOI2011]迷宫探险

这是一个单人游戏。

游戏开始时，玩家控制的人物出生在迷宫的某个位置，玩家的目标是控制人物走到迷宫的某个出口（出口可能有多个）。

迷宫里有 类陷阱（用 A,B,C……表示，相同字母代表相同类型的陷阱），每类陷阱可能是有害的或无害的，而在游戏开始时玩家并不知道哪些陷阱是有害的，哪些是无害的。

同一类陷阱的状态相同，即用同一个字母标志的陷阱要么全部有害，要么全部无害，不会发生一部分有害而另一部分无害的情况。任何陷阱状态的组合都有一个发生概率，考虑下例：

当 时，迷宫内共有两类陷阱，分别用 A 和 B 表示，陷阱状态的组合共有 种：-

• A 是无害陷阱，B 是无害陷阱。
• A 是有害陷阱，B 是无害陷阱；
• A 是无害陷阱，B 是有害陷阱；
• A 是有害陷阱，B 是有害陷阱；

下列表格是一个合法的概率表格：

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

是这样生成的：

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

设 ，则陷阱状态组合 出现的概率为 。

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

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

迷宫可以看作 的方格地图，每个元素可能是：

• .：表示这是平地，可以通过；
• #：表示这是墙，不能通过；
• A，B ，C……：表示这是一个陷阱；
• $：表示这是起点，地图中有且仅有一个；
• @：表示这是终点，地图中可以有多个，也可以一个也没有。

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

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

第一行包含 个整数，分别表示 ； 下面 行每行 个字符描述迷宫地图； 最后一行包含 个非负整数描述数组 ，数组下标从 开始。

仅包含一个数字，表示在执行最优策略时，人物活着走出迷宫的概率。四舍五入保留3位小数。

样例输入 #1

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

样例输出 #1

0.600

【样例说明 1】

向右边走，经过 B ，B 为有害陷阱的概率为 ，若 B 为有害陷阱那么人物就死掉了，游戏失败，否则玩家得知 B 是无害陷阱，继续经过另一个 B 达到终点，胜利的概率为 。

样例输入 #2

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

样例输出 #2

0.800

【样例说明 2】

向左边走，经过 A，A 为有害陷阱的概率为 。若 A 为有害陷阱，那么损失一点生命，转到右边尝试 B ，要想成功到达终点，此时 B 必须为无害陷阱，而在 A是有害陷阱的前提下，B 是无害陷阱的概率是 ，故这种情况发生的概率为 。若 A是无害陷阱，玩家可以控制人物连续通过两个 A 到达终点，这种情况发生的概率 。所以答案为 。

样例输入 #3

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

样例输出 #3

1.000

【样例说明 3】

玩家控制的人物有 点生命，但最多只需要经过两个陷阱，所以任意选左路或右路走过去就可以到达终点了。

样例输入 #4

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

样例输出 #4

0.858

，且至少有一个

第一轮day2