#P2489. [SDOI2011] 迷宫探险

    ID: 1497 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp搜索2011线段树各省省选山东

[SDOI2011] 迷宫探险

题目背景

题目描述

这是一个单人游戏。

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

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

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

k=2k=2 时,迷宫内共有两类陷阱,分别用 AB 表示,陷阱状态的组合共有 44 种:-

  • A 是无害陷阱,B 是无害陷阱。
  • A 是有害陷阱,B 是无害陷阱;
  • A 是无害陷阱,B 是有害陷阱;
  • A 是有害陷阱,B 是有害陷阱;

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

A 是无害陷阱 A 是有害陷阱
B 是无害陷阱 36%36\% 24%24\%
B 是有害陷阱 24%24\% 16%16\%

k=3k=3 时,会有 88 种不同的陷阱状态组合,如果我们依然坚持使用概率表格,那么这个表格将会是三维的(2×2×22\times 2 \times 2,每一维对应着一类陷阱)。当 k3k\ge 3 时,这将使得题目难以描述。因此我们使用一个大小为 2k2^{k} 的数组 pp 来描述每种情况发生的可能性,pp 的下标范围为 02k10\sim 2^{k}-1

pp 是这样生成的:

对于每个可能的陷阱状态组合,考虑所有 kk 类陷阱,令 11 表示某个陷阱有害,00 表示某个陷阱无害,把 A 作为二进制数的第 00 位(从右边开始计数),B 作为第 11 位,C 作为第 22 位……通过以上操作,我们可以得到一个 kk 位的二进制数,把它转化成十进制后,2k2^{k} 种陷阱状态的组合将会与整数 02k10\sim2^{k}-1 一一对应。

S=i=02k1piS = \displaystyle\sum_{i=0}^{2^k-1} p_i,则陷阱状态组合 ii 出现的概率为 piS\dfrac {p_{i}} {S}

上述表格对应的一个合法数组 pp36,24,24,1636,24,24,16

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

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

迷宫可以看作 m×nm\times n 的方格地图,每个元素可能是:

  • .:表示这是平地,可以通过;
  • #:表示这是墙,不能通过;
  • ABC……:表示这是一个陷阱;
  • $:表示这是起点,地图中有且仅有一个;
  • @:表示这是终点,地图中可以有多个,也可以一个也没有。

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

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

输入格式

第一行包含 44 个整数,分别表示 m,n,k,Hm,n,k,H

下面 mm 行每行 nn 个字符描述迷宫地图;

最后一行包含 2k2^{k} 个非负整数描述数组 pp,数组下标从 00 开始。

输出格式

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

4 3 2 1
.$.
A#B
A#B
.@.
30 30 20 20
0.600
4 3 2 2
.$.
A#B
A#B
.@.
30 30 20 20
0.800
4 3 2 3
.$.
A#B
A#B
.@.
30 30 20 20
1.000
4 3 3 2
.$.
A#B
A#C
@@@
143 37 335 85 95 25 223 57
0.858

提示

【样例说明 1】

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

【样例说明 2】

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

【样例说明 3】

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

【数据范围与约定】

测试点编号 mm nn kk HH
11 2929 2828 55 11
22 2828 2020 44
33 2525 3030 11
44 22
55 33
66 55 44 44
77 1212 1111 55
88 1919 1717 55 33
99 2323 2525 44
1010 3030 2929 55

对于 100%100\% 的数据,1m301\le m\leq 301n291\le n\leq 29k5k\leq 5H5H\leq 50pi1050\leq p_i\leq 10^5,且至少有一个 pi>0p_i\gt0