#1242. 2246. [SDOI2011]迷宫探险

2246. [SDOI2011]迷宫探险

#2246. [SDOI2011]迷宫探险

题目描述

这是一个单人游戏。

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

当k=2时,迷宫内共有两类陷阱,分别用"A"和"B"表示,陷阱状态的组合共有4种:

1、"A"是无害陷阱,"B"是无害陷阱。

2、"A"是有害陷阱,"B"是无害陷阱;

3、"A"是无害陷阱,"B"是有害陷阱;

4、"A"是有害陷阱,"B"是有害陷阱;

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

|

"A"是无害陷阱

|

"A"是有害陷阱

---|---|---

"B"是无害陷阱

|

36%

|

24%

"B"是有害陷阱

|

24%

|

16%

当K=3时,会有8种不同的陷阱状态组合,如果我们依然坚持使用概率表格,那么这个表格将会是三维的(222,每一维对应着一类陷阱)。当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出现的概率为Pi / S。上述表格对应的一个合法数组P是:

P0 =36

P1 =24

P2 =24

P3=16

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

P0=72

P1=48

P2=48

P3=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位小数。

样例

样例输入

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

【样例输入1】  

4 3 2 1  

.$.  

A#B  

A#B  

.@.  

30 30 20 20  

【样例输出1】  

0.600  

【样例说明1】  

向右边走,经过“B”,“B”为有害陷阱的概率为 (20+20)/(30+30+20+20=)=0.4,若“B”为有害陷阱那么人物就死掉了,游戏失败,否则玩家得知“B”是无害陷阱,继续经过另一个“B”达到终点,胜利的概率为0.6。  

【样例输入2】  

4 3 2 2  

.$.  

A#B  

A#B  

.@.  

30 30 20 20  

【样例输出2】  

0.800  

【样例说明2】  

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

【样例输入3】  

4 3 2 3  

.$.  

A#B  

A#B  

.@.  

30 30 20 20  

【样例输出3】  

1.000  

【样例说明3】  

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

【样例输入4】  

4 3 3 2  

.$.  

A#B  

A#C  

@@@  

143 37 335 85 95 25 223 57  

【样例输出4】  

0.858

样例输出

数据范围与提示

m<=30,N<=29,K<=5,H<=5,0<=pi<=10^5 ,且至少有一个pi>0