这是一个单人游戏。
游戏开始时,玩家控制的人物出生在迷宫的某个位置,玩家的目标是控制人物走到迷宫的某个出口(出口可能有多个)。
迷宫里有 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×2×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=i=0∑2k−1pi,则陷阱状态组合 i 出现的概率为 Spi。
上述表格对应的一个合法数组 p 为 36,24,24,16。
当然同一个概率表格可能会对应多个数组 p(事实上有无数个数组 p 能够迎合表格数据),例如上述表格同时也对应着下面的数组 p:72,48,48,32。
玩家控制的人物初始情况下有 H 点生命,当人物踏上某个陷阱时,如果这个陷阱是有害的,那么会损失 1 点生命,否则这个陷阱是无害的,不损失生命。无论上述哪种情况发生,玩家会立刻得到这个陷阱的信息(有害或无害)。一旦生命小于等于 0,玩家控制的人物会立刻死亡。
迷宫可以看作 m×n 的方格地图,每个元素可能是:
.
:表示这是平地,可以通过;#
:表示这是墙,不能通过;A
,B
,C
……:表示这是一个陷阱;@
:表示这是终点,地图中可以有多个,也可以一个也没有。人物可以向上下左右四个方向行走,不可以走对角线,也不可以走出地图。
给定 m×n的地图、k、h 以及大小为 2k 的概率数组。你的任务是求出在执行最优策略时,人物能活着走出迷宫的概率。
第一行包含 4 个整数,分别表示 m,n,k,H; 下面 m 行每行 n 个字符描述迷宫地图; 最后一行包含 2k 个非负整数描述数组 p,数组下标从 0 开始。
仅包含一个数字,表示在执行最优策略时,人物活着走出迷宫的概率。四舍五入保留3位小数。
m≤30,n≤29,k≤5,H≤5,0≤pi≤105 ,且至少有一个 pi>0
向右边走,经过 B
,B
为有害陷阱的概率为 (30+30+20+20)(20+20)=0.4,若 B
为有害陷阱那么人物就死掉了,游戏失败,否则玩家得知 B
是无害陷阱,继续经过另一个 B
达到终点,胜利的概率为 0.6。
向左边走,经过 A
,A
为有害陷阱的概率为 (30+30+20+20)(30+30)=0.5。若 A
为有害陷阱,那么损失一点生命,转到右边尝试 B
,要想成功到达终点,此时 B
必须为无害陷阱,而在 A
是有害陷阱的前提下,B
是无害陷阱的概率是 (30+20)30=0.6,故这种情况发生的概率为 0.5×0.6=0.3。若 A
是无害陷阱,玩家可以控制人物连续通过两个 A
到达终点,这种情况发生的概率 0.5。所以答案为 0.3+0.5=0.8。
玩家控制的人物有 3 点生命,但最多只需要经过两个陷阱,所以任意选左路 或右路走过去就可以到达终点了。