MediumRating 1666
1162. As Far from Land as Possible
arraydynamic-programmingbreadth-first-searchmatrix
解題說明
As Far from Land as Possible
題目描述：
給定一個 n x n 的矩陣 grid，其中 1 代表陸地、0 代表水域。求水域格子到最近陸地的最大曼哈頓距離。如果全是陸地或全是水域，返回 -1。
解題思路： 多源 BFS：
這是典型的「多源最短路」問題。
- 將所有陸地格子（值為
1）加入 BFS 佇列作為起始源點。 - 逐層向外擴展（每層距離 +1），每到達一個水域格子就記錄其距離。
- BFS 結束時，最後一個被訪問的水域格子的距離即為答案。
多源 BFS 保證每個水域格子第一次被訪問時記錄的距離就是到最近陸地的最短距離。
C++ 解法
複雜度分析
時間複雜度：O(n^2) — 每個格子最多被訪問一次。
空間複雜度：O(n^2) — BFS 佇列最差情況存放 O(n^2) 個格子。
虛擬碼
1. Add all land cells (value 1) to BFS queue. 2. If queue is empty or full (all land/all water), return -1. 3. BFS level-by-level: a. For each cell, explore 4 neighbors. b. If neighbor is water (0), set its distance = current + 1, add to queue. c. Track maximum distance. 4. Return maximum distance.
其他解法
動態規劃（兩次掃描）：O(n^2) 時間、O(1) 額外空間。第一次從左上到右下掃描，更新每個水域格子到左方和上方最近陸地的距離。第二次從右下到左上掃描，更新到右方和下方最近陸地的距離。取所有水域格子的最大距離。不需要 BFS 佇列。
暴力法：O(n^4) 時間。對每個水域格子，遍歷所有陸地格子計算距離取最小值。效率極低。
延伸思考
- 為什麼多源 BFS 比對每個水域格子分別做 BFS 更高效？時間複雜度差多少？
- 動態規劃解法只需兩次掃描就能得到正確答案，為什麼兩個方向就足夠了？
- 如果距離改為歐氏距離而非曼哈頓距離，BFS 還適用嗎？需要什麼替代方法？