我遇到了一个我无法解决的问题。我正在尝试编写一个程序来解决其中有地雷的 m x n 网格迷宫。棘手的部分是玩家/迷宫跑者有 L >= 1 条生命，这意味着他们在死于下一个地雷之前最多可以踩到 L - 1 颗地雷。
更多详情:
-每个单元格都可以连接到任何相邻的单元格。所有连接都是双向的。
-我们可以假设迷宫在给定生命数的情况下从头到尾有一条正确的路径。
-迷宫可以包含环路或“岛”，其中从给定单元格的两条路径通向同一单元格。
我目前的想法:
我尝试了多种方法来解决这个问题。有一个明显的蛮力解决方案，它涉及遍历每条可能的路径并选择距离最短的路径。但那是指数时间。我觉得可能有类似 Dijkstra 或 A* 的解决方案导致 O(n + vlogv) 时间。 Vanilla Dijkstra 或 A* 不会导致此问题的解决方案，因为图的状态会根据它的遍历方式有效地改变。我也尝试过各种广度优先搜索+回溯开始使用优先队列。经过进一步调查，这些方案可能导致指数时间。
到目前为止，我提出的最有前途的想法涉及将每个迷宫解析成一个图并执行修改后的 Dijkstra。每个具有三个或更多连接的单元将是一个节点。具有两个连接的每个单元都是路径的一部分。可以丢弃具有一个连接的每个单元格。最终结果是一个图表。然后你执行类似于Dijkstra的操作，但我还没有明确解决方案。
我只能猜测这个解决方案需要一种算法，该算法在最好的情况下是高效的，但在最坏的情况下可能会呈指数增长。
最佳答案
您绝对应该选择动态规划 (DP) 风格的算法。
如果您在此处添加了一个示例迷宫矩阵，那么我将很容易理解这个问题。
您的问题与this 非常相似.因此，请阅读它。但在直接转到解决方案之前，请阅读 this tutorial .
关于algorithm - 在有地雷和有限生命的迷宫中找到最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43084238/