題目描述:給定一個只含 0 和 1 的矩陣,對每個格子計算其到最近 0 的距離(曼哈頓距離)。
解題思路:多源 BFS 是最優解法。將所有 0 的位置同時加入佇列作為初始狀態,距離設為 0;1 的格子初始距離設為 INT_MAX(未訪問)。BFS 層層向外擴展,每次更新鄰居距離為當前距離 + 1。由於 BFS 保證最短路徑,每個格子第一次被訪問時即得到正確的最短距離。
時間複雜度:O(m × n) — 每個格子最多進出佇列一次。
空間複雜度:O(m × n) — dist 矩陣與 BFS 佇列各佔 O(m × n) 空間。
1. Initialize dist matrix with INT_MAX; set dist[i][j] = 0 for all 0 cells
2. Add all 0 cells to BFS queue
3. While queue not empty:
a. Pop cell (r, c)
b. For each neighbor (nr, nc) in 4 directions:
- If dist[nr][nc] > dist[r][c] + 1:
* Update dist[nr][nc] = dist[r][c] + 1
* Push (nr, nc) to queue
4. Return dist動態規劃 O(m × n):兩次掃描(左上→右下、右下→左上),取四方向最小距離 + 1 — 與 BFS 同等時間複雜度,但實作更簡潔,不需佇列。
單源 BFS O(m × n × k):從每個 1 的格子做 BFS 找最近的 0 — 正確但極慢,在最壞情況下為 O(m² × n²),不可接受。