我最近出現了一個求職面試，當時我被問到流行的RAT IN A MAEE問題，其中有一個由2維數組表示的迷宮，分別包含0和1的開放路徑和牆，我們必須打印最短路徑。回溯 - 如何解決「迷宮中的老鼠」這個變種？
我使用回溯解決了問題，並且還打印了所有可能的路徑。
但隨後採訪者提高了韌性水平，並要求我用一種新的條件來解決同一個問題，在這種情況下，老鼠可以絆倒「K」數量的牆，K由用戶輸入。
現在我嘗試了很多，但無法弄清楚如果跳閘K牆被允許，如何找到最短路徑。我想是否可以通過動態規劃解決，但最終無法實現。
面試官也沒有透露解決方案。 任何人都可以解釋這個問題的解決方案？
您可以使用breadth-first search解決此問題。
如果您還不夠熟悉，您可能需要閱讀上面鏈接的基本BFS算法，因爲以下內容主要是基於此。
對於每一個細胞，我們需要存儲牆，我們已經經歷了數量達到那個細胞 - 稱之爲walls。
從包含我們的起始單元格的隊列開始。
讓起始單元的walls爲0。
重複設置當前單元格等於隊列的第一個元素（我們刪除）。
如果當前單元格是目標單元格，則打印出路徑，我們就完成了。
如果當前單元是一堵牆，增加current.walls由1
如果current.walls > K，什麼也不做。
對於每個鄰居：（牆壁和開放式的細胞）
如果neighbour.walls將不會被初始化（這意味着我們還沒有去過那裏之前）或current.walls < neighbour.walls（意爲新的路徑具有更少的壁），
然後設置neighbour.wall = current.walls並將neighbour添加到隊列中。
居然能打印出路徑，創建地圖的任何細胞映射其walls我們從來到那裏的細胞（和它的walls）。它不會將單元映射到前一個單元格，因爲如果路徑中的前一個單元格的值較低，則可以覆蓋K。
您還可以將整個路徑，但這是少了一大堆高效。
時間複雜度爲O(rows*columns*K)和空間複雜度爲O(rows*columns)。
很多這裏的複雜性是需要處理這樣的情況下的結果：
（你能想象一個大電網的這是一部分）
如果我們有一個足夠大的K，我們剛剛跨過兩個牆（綠色通道）和2點移動到右上角的電池。
如果K不夠大，我們需要繞過去（藍色路徑），將於4個移動。
因此，我們做一個常規的BFS，但也要記錄每個單元有多少個隔牆，所以如果我們在四處走動後到達右上角的單元，我們會看到它先前已經達到穿過2個牆壁（而不是當前的0），因此，如果使用2個牆壁的路徑最終需要穿過太多的牆壁，我們會繼續前進。
通過「跳閘」的牆壁，你的意思是通過移動或刪除牆壁？ – Dukeling
這是您可以用Dijkstra解決的一個變體，其中每個節點還存儲哪些牆已被移除。 –