题面

P2489 [SDOI2011] 迷宫探险

feicheng @ 2021-09-12 15:20:30

题目描述

这是一个单人游戏。

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

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

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

k=2 时,迷宫内共有两类陷阱,分别用 AB 表示,陷阱状态的组合共有 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

对于每个可能的陷阱状态组合,考虑所有 $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$ 开始。 ## 输出格式 仅包含一个数字,表示在执行最优策略时,人物活着走出迷宫的概率。四舍五入保留3位小数。 ## 提示 $m\leq 30,n\leq 29,k\leq 5,H\leq 5,0\leq p_i\leq 10^5$ ,且至少有一个 $p_i\gt0

【样例说明 1】

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

【样例说明 2】

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

【样例说明 3】

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


by feicheng @ 2021-09-12 15:21:02

## 题目描述
这是一个单人游戏。

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

迷宫里有 $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$ 开始。
## 输出格式
仅包含一个数字,表示在执行最优策略时,人物活着走出迷宫的概率。四舍五入保留3位小数。

## 提示
$m\leq 30,n\leq 29,k\leq 5,H\leq 5,0\leq p_i\leq 10^5$ ,且至少有一个 $p_i\gt0$ 

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

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

## 【样例说明 3】

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

by feicheng @ 2021-09-12 15:23:41

@SSerxhs


by _Veritas @ 2021-09-12 15:38:45

Wow.


by SSerxhs @ 2021-09-13 10:20:59

@飞丞 fixed。缺少每组数据的说明


by feicheng @ 2021-09-13 11:03:24

@SSerxhs

|测试点编号  | $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$ |

by feicheng @ 2021-09-13 11:07:11

@SSerxhs 另外,根据表格来说,n 的范围应该是 1\sim 30,可否修改一下


by SSerxhs @ 2021-09-13 11:28:23

@飞丞 fixed

注意范围一般写法如下

对于 $100\%$ 的数据,$1\le m\leq 30$,$1\le n\leq 29$,$k\leq 5$,$H\leq 5$,$0\leq p_i\leq 10^5$,且至少有一个 $p_i\gt0$ 。

by feicheng @ 2021-09-13 11:51:25

@SSerxhs ok


|