MediumRating 1608

3286. Find a Safe Walk Through a Grid

arraybreadth-first-searchgraphheap-priority-queuematrixshortest-path

解題說明

Find a Safe Walk Through a Grid

題目描述：給定一個 m×n 的二維網格 grid，其中 grid[i][j] 為 0 或 1。值為 1 的格子是不安全的，經過時會消耗 1 點生命值；值為 0 的格子是安全的，不消耗生命值。你有初始生命值 health，從 (0,0) 走到 (m-1,n-1)，每步可往上下左右移動。到達終點時生命值必須嚴格大於 0。判斷是否存在一條安全路徑。

解題思路：這是一個 0-1 BFS 問題。將格子的值視為邊權（0 或 1），用雙端佇列（deque）實作 0-1 BFS，找出從 (0,0) 到 (m-1,n-1) 的最小生命消耗。若起點的消耗加上路徑消耗嚴格小於 health，則可達。注意起點 (0,0) 本身的值也要計入消耗。

C++ 解法

複雜度分析

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

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

虛擬碼

1. Initialize dist[0][0] = grid[0][0], all others = INF
2. Push (0, 0) to deque
3. While deque is not empty:
   a. Pop (x, y) from front
   b. For each neighbor (nx, ny):
      i.  new_dist = dist[x][y] + grid[nx][ny]
      ii. If new_dist < dist[nx][ny]:
          Update dist[nx][ny]
          If grid[nx][ny] == 0: push to front
          Else: push to back
4. Return dist[m-1][n-1] < health

其他解法

Dijkstra O(m × n × log(m × n))：將每個格子視為一個節點，權重為目標格子的值，使用 Dijkstra 求最短路。正確但多了 log 因子，0-1 BFS 在此題更高效。

動態規劃 O(m × n)：若只允許向右或向下移動，可用簡單 DP。但此題允許四個方向，DP 無法直接適用（需要最短路演算法）。

延伸思考

如果格子的消耗值不限於 0/1 而是任意正整數，應該用什麼演算法？
如果可以在路徑中「回復」生命值（某些格子值為負），0-1 BFS 還適用嗎？
如果要求找出所有最小消耗的路徑（不只是判斷可達性），如何修改？

Find a Safe Walk Through a Grid — CaffeCode