題目描述:
給定一個 n x n 的矩陣 grid,其中 1 代表陸地、0 代表水域。求水域格子到最近陸地的最大曼哈頓距離。如果全是陸地或全是水域,返回 -1。
解題思路: 多源 BFS:
這是典型的「多源最短路」問題。
1)加入 BFS 佇列作為起始源點。多源 BFS 保證每個水域格子第一次被訪問時記錄的距離就是到最近陸地的最短距離。
時間複雜度: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) 時間。對每個水域格子,遍歷所有陸地格子計算距離取最小值。效率極低。