算法最短路徑與表述爲遵循contraint，BFS或DFS

Question

問：

拿到一張地圖，它有它的一些障礙。給定一個起點S 和終點E，找到從S到E的最短路徑。注意，你可以從S中選擇任意（4）方向的 ，但是在這個過程中，你只能從前一個方向直接走 ，除非你遇到了障礙。

我很困惑這個約束，但過程中，你只能

從以前的方向直行，除非你打的障礙。

這是否意味着直截了當的BFS將無法解決這個問題？修改後的BFS或DFS能夠爲此找到解決方案嗎？

索賠：我正在尋找一個解決方案，只是一些提示或想法。

Answer 1

是的，一個簡單的BFS可以在任何細胞中轉動，而在這個問題中，只有當你碰到牆時才能轉動。

該問題仍然可以通過修改後的圖上的BFS來解決。爲了正確模擬約束，您可以創建輔助頂點，從中只能沿一個方向移動。

或者，您可以建立另一個帶有加權邊的新圖，並在其上使用更一般的最短路徑算法（Dijkstra或Ford-Bellman）。具體來說，當你站在一個單元格中並選擇一個方向時，在單元格上繪製一個邊緣，在那裏你可以再次改變方向。該邊的重量只是兩個單元之間的直線路徑的長度。