HardRating 2069

1368. Minimum Cost to Make at Least One Valid Path in a Grid

arraybreadth-first-searchgraphheap-priority-queuematrixshortest-path

解題說明

Minimum Cost to Make at Least One Valid Path in a Grid

題目描述：給定一個 m × n 的網格，每個格子有一個方向（1=右, 2=左, 3=下, 4=上）。你可以花費 1 的代價改變任意格子的方向。找出從左上角 (0,0) 到右下角 (m-1,n-1) 的最小代價路徑。

解題思路：這是一個 0-1 BFS 問題。沿著格子本身指示的方向移動代價為 0，改變方向移動代價為 1。使用雙端佇列（deque）實現 0-1 BFS：代價為 0 的鄰居放到佇列前端，代價為 1 的放到後端。這樣可以保證佇列中的元素按代價排序，等效於 Dijkstra 但更高效。

C++ 解法

複雜度分析

時間複雜度：O(m × n) — 每個格子最多被處理一次，0-1 BFS 的標準複雜度

空間複雜度：O(m × n) — 距離矩陣和雙端佇列

虛擬碼

1. Initialize dist[m][n] with infinity, dist[0][0] = 0
2. Push (0, 0) to front of deque
3. While deque is not empty:
   a. Pop front cell (x, y)
   b. For each of 4 directions d:
      - Calculate neighbor (nx, ny)
      - cost = 0 if grid[x][y] matches direction d+1, else 1
      - If dist[x][y] + cost < dist[nx][ny]:
        - Update dist[nx][ny]
        - Push to front if cost = 0, back if cost = 1
4. Return dist[m-1][n-1]

其他解法

方法二：Dijkstra + 優先佇列 將每個格子視為圖的節點，邊權為 0（順方向）或 1（改方向），用 Dijkstra 求最短路。時間複雜度 O(mn log(mn))，比 0-1 BFS 多一個 log 因子。

方法三：動態規劃 + 多次鬆弛 類似 Bellman-Ford 的思路，反覆從四個方向鬆弛直到不再更新。正確性有保證但效率較低。

延伸思考

如果每個格子改變方向的代價不同（例如依據方向差異），如何修改演算法？
如果需要輸出具體的最小代價路徑（而不只是代價值），如何追蹤路徑？
0-1 BFS 和 Dijkstra 演算法在什麼情況下各有優勢？

Minimum Cost to Make at Least One Valid Path in a Grid — CaffeCode