我遇到了一个问题，我在解决方面遇到了一些麻烦 . 我正在尝试编写一个程序来解决一个m网格迷宫，其中有地雷 . 棘手的部分是玩家/迷宫跑者的生命数L> = 1，这意味着他们可以踩下最多的L - 1地雷，然后才能在下一枚地雷上死亡 .
更多详情：
-
每个单元可以连接到任何相邻单元 . 所有连接都是双向的 .
-
我们可以假设迷宫在给定生命数量的情况下从开始到结束都有正确的路径 .
-
迷宫可以包含循环或“岛屿”，其中来自给定细胞的两条路径通向同一细胞 .
我目前的想法：
我已经尝试了各种方法来解决这个问题 . 有明显的蛮力解决方案，包括遍历每条可能的路径，并采取距离最短的路径 . 但这是指数时间 . 我觉得可能有类似Dijkstra或A *的解决方案导致O（n vlogv）时间 . Vanilla Dijkstra或A *不会导致此问题的解决方案，因为图形的状态根据遍历的方式有效地改变 . 我还尝试了各种广度优先搜索跟踪以开始使用优先级队列 . 经过进一步调查，这些方案可以导致指数时间 .
到目前为止，我提出的最有希望的想法是将每个迷宫解析成图形并执行修改后的Dijkstra . 具有三个或更多连接的每个单元将是节点 . 具有两个连接的每个单元是路径的一部分 . 可以丢弃具有一个连接的每个单元 . 最终结果是图表 . 然后你执行类似于Dijkstra的事情，但我还没有澄清一个解决方案 .
我只能猜测这个解决方案需要一种在最佳情况下有效的算法，但在最坏的情况下可能会成为指数 .
3 回答
你绝对应该采用动态编程（DP）风格的算法 .
如果您在这里添加了一个示例迷宫矩阵，那么我很容易理解这个问题 .
你的问题与this非常相似 . 所以请仔细阅读 . 但在直接进入解决方案之前，请阅读this tutorial .
迷宫遍历期间的状态由单元格和剩余生命数组成，因此您可以将一组可能的遍历表示为具有
N*L顶点的图形（其中N是单元格数） .为了略微简化，您可以将所有L个最终顶点折叠成单个最终顶点，因为遍历结束时剩余生命的数量是无关紧要的 .
然后，您可以使用任何最短路径算法来查找解决方案 .
变换后的图形具有大约L倍的顶点和L倍的边数，因此它将复杂度乘以L² .
将迷宫视为每个清晰方块的节点，以及每对连接方块之间的边缘 .
设N是图中节点的数量 . 为每个边分配N * k 1的成本，其中k是它接触的地雷数（0,1或2） . 这确保了在地雷上移动比在清澈的广场上移动花费多2N .
现在使用Dijkstra算法找到通过图表的最短路径 .