迷宮中的最短路徑允許穿過有限數量的牆？

Question

沒有穿牆的能力，我認爲這是標準的Dijkstra的問題。但是，如果我給X次繞過/穿過牆壁，我如何對它進行建模以應用Dijkstra算法？

Answer 1

假設您的迷宮用圖表表示：創建該圖形的X + 1個副本，併爲與它們之間的牆壁相鄰的單元格創建級別和i + 1級別之間的有向邊。最後合併所有的出口。

從實際的角度來看，當然您不需要創建圖的副本，只需跟蹤（頂點，水平）的有序對。