带生命值损耗的迷宫最短路径：存活约束下的求解方案

咱们一步一步来拆解这个问题。核心痛点就是普通的Dijkstra算法只盯着「路径最短」，完全不管中途会不会掉血掉死。所以得调整思路，把剩余生命值和坐标绑定成一个完整状态来追踪——毕竟同一个格子，剩1血和剩3血能走的后续路径完全不是一回事。

1. 重新定义「节点状态」 #

别再只拿(x,y)当一个节点了，咱们把状态改成(x, y, 当前剩余生命值)，而且这个生命值必须大于0（走到终点时只要活着就行，剩1血也没问题）。举个例子：你剩2血到了(2,3)，和剩4血到(2,3)，这是两个完全独立的状态，后者显然能应对更多扣血的格子。

2. 改造Dijkstra算法（核心思路） #

因为咱们的目标还是最短路径，所以Dijkstra的优先级队列（小顶堆）思路依然适用，但队列里存的元素得变：每个元素是(当前路径长度, x, y, 当前剩余生命值)，每次优先弹出路径最短的状态来扩展。

同时要维护两个关键记录：

• 一个dist数组（或者哈希表），记录到达(x,y)且剩余hp时的最短路径长度；
• 对每个(x,y)，额外记录「到达这里时能拥有的最大剩余生命值」——如果新状态的路径长度和已记录的一样，但生命值更高，或者路径更短且生命值够活，就更新状态加入队列。

扩展邻居的时候要做这几步检查：

• 先看邻居是不是障碍物，是就直接跳过；
• 计算新生命值：新生命值 = 当前生命值 - 邻居格子的扣血值（没扣血的话就等于当前生命值）；
• 必须保证新生命值 > 0（如果是终点，只要≥1就行，毕竟活着到终点就达标）；
• 如果这个新状态的路径长度比已记录的更短，或者同长度但生命值更高（后续容错空间更大），就把它放进优先级队列。

3. 终止条件 #

当我们第一次从队列里取出终点E(x2,y2)的状态时，对应的路径长度就是满足存活要求的最短路径——因为Dijkstra是按路径长度从小到大处理的，第一次碰到终点肯定是最短的合法路径。

4. 实用优化点 #

• 对每个(x,y)，如果已经有一条路径：路径长度更短，而且剩余生命值比当前新状态还高，那这个新状态直接扔了就行——它既没路径优势，也没生存优势，后续不可能走出更好的结果；
• 初始状态就是(x1,y1, 5)，路径长度为0。

为啥不用普通BFS？ #

普通BFS是按路径长度逐层扩展的，看似能找最短路径，但它没法处理「同一格子不同生命值」的情况。比如你可能先以剩1血的状态走到某个格子，之后又以剩3血的状态走到同一个格子——后者路径长度一样，但生存能力强得多，可普通BFS如果标记(x,y)已访问，就会错过这个更优的状态。

内容的提问来源于stack exchange，提问作者Ben G