迷宫中的最短路径允许穿过有限数量的墙？

Question

没有穿墙的能力，我认为这是标准的Dijkstra的问题。但是，如果我给X次绕过/穿过墙壁，我如何对它进行建模以应用Dijkstra算法？

Answer 1

假设您的迷宫用图表表示：创建该图形的X + 1个副本，并为与它们之间的墙壁相邻的单元格创建级别和i + 1级别之间的有向边。最后合并所有的出口。

从实际的角度来看，当然您不需要创建图的副本，只需跟踪（顶点，水平）的有序对。