我遇到了一个问题，我在解决时遇到了一些问题。我正在尝试编写一个程序来解决一个包含地雷的 m x n 网格迷宫。棘手的部分是玩家/迷宫跑者的生命数为 L>= 1，这意味着他们最多可以踩到 L - 1 枚地雷，然后才能死在下一个地雷上。
更多详情：
-每个电池都可以连接到任何相邻的电池。所有连接都是双向的。
-我们可以假设迷宫从头到尾都有正确的路径，给定的生命数量。
迷宫可以包含循环或"孤岛"，其中来自给定单元格的两条路径通向同一单元格。
我目前的想法：
我已经尝试了多种方法来解决这个问题。有一个明显的蛮力解决方案，它涉及遍历每条可能的路径并采取距离最短的路径。但那是指数级的时间。我觉得可能有一个类似Dijkstra或类似A*的解决方案会导致O(n + vlogv)时间。Vanilla Dijkstra 或 A* 不会解决此问题，因为图形的状态会根据遍历方式而有效变化。我还尝试了各种广度优先搜索+回溯以开始使用优先级队列。经过进一步调查，这些方案可能会导致指数时间。
到目前为止，我想出的最有前途的想法是将每个迷宫解析为一个图形并执行修改后的Dijkstra。具有三个或更多连接的每个单元将是一个节点。具有两个连接的每个像元都是路径的一部分。可以丢弃具有一个连接的每个单元。最终结果是一个图表。然后，您执行类似于Dijkstra的操作，但我尚未澄清解决方案。
我只能猜测这个解决方案需要一个在最好的情况下有效的算法，但在最坏的情况下可能会变成指数级的算法。
你绝对应该选择动态规划(DP)风格的算法。
如果您在此处添加一个示例迷宫矩阵，那么我将很容易理解问题。
你的问题与此非常相似。所以请阅读它。但在直接转到解决方案之前，请阅读本教程。
迷宫遍历期间的状态由像元和剩余的生命数组成，因此您可以将可能的遍历集表示为具有N*L顶点的图形(其中 N 是像元数)。
为了简化一点，您可以将所有 L 最终顶点折叠成单个最终顶点，因为导线末端的剩余生命数无关紧要。
然后，您可以使用任何最短路径算法来查找解决方案。
变换后的图形具有大约 L 倍的顶点数和 L 倍的边数，因此它将复杂性乘以 L²。
将迷宫视为一个图形，每个透明正方形都有一个节点，每对连接的正方形之间都有一个边。
设 N 为图中的节点数。 为每个边分配 N*k+1 的成本，其中 k 是它接触的地雷数量(0、1 或 2)。 这确保了在地雷上移动的成本比在清晰的正方形上移动要多花费 2N。
现在使用 Dijkstra 的算法找到通过图形的最短路径。