问题理解

我们有一个迷宫，包含：

• 起点 $、终点 @、墙 #、平地 .、以及 $K$ 类陷阱（字母 A,B,C,…）
• 每类陷阱的状态（有害/无害）在游戏开始时按给定概率分布随机确定，但玩家未知
• 玩家初始生命 $H$，踩到有害陷阱扣 1 生命，生命 ≤ 0 时死亡
• 踩到陷阱后立刻获知该类陷阱的真实状态
• 目标：在最优策略下，求玩家能活着到达任意终点的概率

---

关键观察

1. 状态空间
   玩家的状态由三部分组成：

   • 位置 $(x,y)$
   • 剩余生命值 $h$
   • 已知的陷阱信息（哪些陷阱已探明，以及它们是 harmful 还是 safe）

2. 概率更新（贝叶斯推理）
   设初始时，所有 $2^K$ 种陷阱状态组合的概率为 $P_0, P_1, \dots, P_{2^K-1}$（由 $p$ 数组归一化得到）。
   当玩家探明某类陷阱的状态后，概率分布会收缩到满足该条件的那些组合上，并重新归一化。

3. 最优策略原则
   在每个状态下，玩家选择最大化生存概率的移动方向。
   这需要考虑：

   • 不同路径可能遇到的不同陷阱
   • 探明信息对后续决策的价值
   • 生命值的限制

---

状态表示与DP定义

陷阱信息表示

由于 $K \leq 5$，可用 $2K$ 位（或两个 $K$ 位掩码）表示已知信息：

• known_mask：哪些陷阱已探明（1 表示已知）
• harm_mask：已知有害的陷阱（仅对 known_mask 中的位有效）

更简单的做法：用 $3^K$ 种状态表示每类陷阱的知晓情况（未知 / 已知无害 / 已知有害），但 $K=5$ 时 $3^5=243$ 可接受。

DP状态

定义 $dp[x][y][h][s]$ 表示：

• 当前位置 $(x,y)$
• 剩余生命 $h$
• 陷阱信息状态 $s$（编码已知情况） 时，从该状态出发能到达终点的最大概率。

---

状态转移

基本情况

• 若 $(x,y)$ 是终点：$dp = 1.0$
• 若 $h = 0$（已死）：$dp = 0.0$

一般情况

从 $(x,y,h,s)$ 出发，枚举四个移动方向 $(nx,ny)$：

1. 如果是墙或出界：不可走，贡献 0

2. 如果是平地或已知无害陷阱：直接转移到 $(nx,ny,h,s)$，概率不变

3. 如果是已知有害陷阱：转移到 $(nx,ny,h-1,s)$（若 $h>1$，否则死亡）

4. 如果是未知陷阱（设为类型 $t$）：
   需要根据当前概率分布计算期望：

   • 计算在状态 $s$ 下，陷阱 $t$ 为有害的概率 $p_{\text{harm}}$ 和无害的概率 $p_{\text{safe}}$
   • 如果走这里：
     • 以概率 $p_{\text{safe}}$ 探明它为无害，更新状态 $s'$，生命不变，后续概率为 $dp[nx][ny][h][s']$
     • 以概率 $p_{\text{harm}}$ 探明它为有害，生命减 1，更新状态 $s''$，后续概率为 $dp[nx][ny][h-1][s'']$（若 $h>1$，否则为 0）
   • 因此走这里的期望存活概率为： [ p_{\text{safe}} \cdot dp[nx][ny][h][s'] + p_{\text{harm}} \cdot dp[nx][ny][h-1][s''] ]

最优选择

$dp[x][y][h][s]$ 取所有移动方向中的最大值，因为玩家会选择最优动作。

---

概率分布更新方法

给定当前信息状态 $s$（已知某些陷阱的真实情况），我们可以从初始概率分布 $P$ 中筛选出所有符合已知信息的陷阱状态组合，将这些组合的概率重新归一化，得到当前分布。

例如：

• 初始 $P$ 有 $2^K$ 项
• 已知陷阱 A 无害 → 只保留二进制第 0 位 = 0 的项，归一化
• 已知陷阱 B 有害 → 只保留二进制第 1 位 = 1 的项，归一化

在计算 $p_{\text{harm}}$ 和 $p_{\text{safe}}$ 时，只需在当前分布中统计陷阱 $t$ 对应位为 1 的概率和。

---

算法流程

1. 预处理

   • 读入地图，找到起点、终点
   • 归一化 $p$ 得到初始概率分布 $P$
   • 建立陷阱类型到二进制位的映射

2. 记忆化搜索/DP

   • 从起点 $(sx,sy)$，生命 $H$，信息状态 $s=0$（全未知）开始 DFS
   • 用哈希表或数组存储 $dp[x][y][h][s]$
   • 递归计算时，按上述转移方程求最大值

3. 输出
   $dp[sx][sy][H][0]$ 即为答案，保留 3 位小数

---

复杂度分析

• 状态数：$O(m \cdot n \cdot H \cdot 3^K)$
  • $m,n \leq 30$ → $900$
  • $H \leq 5$
  • $K \leq 5$ → $3^5 = 243$
  • 总状态数约 $900 \times 5 \times 243 \approx 10^6$ 量级，可行
• 每个状态转移需 $O(4 \cdot 2^K)$ 计算概率（但 $2^K \leq 32$）

---

样例分析

以样例 2 为例：

• $K=2$，初始分布：$P_{00}=0.3, P_{10}=0.3, P_{01}=0.2, P_{11}=0.2$（归一化后）
• $H=2$
• 起点左右有 A 和 B
• 最优策略：先走左边探 A
  • 若 A 无害（概率 0.5），直接走 A 到达终点 → 概率 0.5
  • 若 A 有害（概率 0.5），生命剩 1，已知 A 有害，更新分布后走右边 B
    • 在 A 有害条件下，B 无害概率 $0.3/(0.3+0.2)=0.6$ → 贡献 $0.5 \times 0.6 = 0.3$
  • 总概率 $0.5 + 0.3 = 0.8$

---

总结

这道题的核心是：

1. 状态设计：将位置、生命、已知信息编码为 DP 状态
2. 贝叶斯更新：根据探明的陷阱信息实时更新概率分布
3. 最优子结构：每个状态下的选择是最大化后续生存概率
4. 记忆化搜索：避免重复计算相同状态

通过将概率推理与图上的动态规划结合，可以求出在最优策略下的生存概率。