給定一個
n x n的網格grid，1代表陸地、0代表水域。求水域格子到最近陸地的曼哈頓距離中，最大的那個值。若全是陸地或全是水域，回傳-1。
Example:
Input: grid = [[1,0,1],[0,0,0],[1,0,1]] Output: 2
Intuition
TIP
多源 BFS — 從所有陸地同時出發，最後被到達的水域格子就是答案。
- 將所有陸地格子作為 BFS 起點（多源 BFS）
- 同時向外擴展，每層距離加一
- 最後一個被訪問到的水域格子的距離就是最大距離
Approaches
⭐ 1. Multi-Source BFS — O(n^2) / O(n^2)
- Idea: 所有陸地同時入隊，BFS 層層擴展，最後一層的距離即為答案
- Time:
O(n^2) - Space:
O(n^2)
class Solution {
fun maxDistance(grid: Array<IntArray>): Int {
val n = grid.size
val queue = ArrayDeque<IntArray>()
for (i in 0 until n) {
for (j in 0 until n) {
if (grid[i][j] == 1) queue.add(intArrayOf(i, j))
}
}
if (queue.size == 0 || queue.size == n * n) return -1
val dirs = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
var dist = -1
while (queue.isNotEmpty()) {
dist++
repeat(queue.size) {
val (r, c) = queue.removeFirst()
for ((dr, dc) in dirs) {
val nr = r + dr
val nc = c + dc
if (nr in 0 until n && nc in 0 until n && grid[nr][nc] == 0) {
grid[nr][nc] = 1
queue.add(intArrayOf(nr, nc))
}
}
}
}
return dist
}
}2. Dynamic Programming — O(n^2) / O(n^2)
- Idea: 兩次掃描：左上到右下、右下到左上，計算每個格子到最近陸地的距離
- Time:
O(n^2) - Space:
O(n^2)
class Solution {
fun maxDistance(grid: Array<IntArray>): Int {
val n = grid.size
val dist = Array(n) { IntArray(n) { n * 2 } }
for (i in 0 until n) {
for (j in 0 until n) {
if (grid[i][j] == 1) dist[i][j] = 0
}
}
// 左上到右下
for (i in 0 until n) {
for (j in 0 until n) {
if (i > 0) dist[i][j] = minOf(dist[i][j], dist[i - 1][j] + 1)
if (j > 0) dist[i][j] = minOf(dist[i][j], dist[i][j - 1] + 1)
}
}
// 右下到左上
var result = -1
for (i in n - 1 downTo 0) {
for (j in n - 1 downTo 0) {
if (i < n - 1) dist[i][j] = minOf(dist[i][j], dist[i + 1][j] + 1)
if (j < n - 1) dist[i][j] = minOf(dist[i][j], dist[i][j + 1] + 1)
if (grid[i][j] == 0) result = maxOf(result, dist[i][j])
}
}
return if (result == n * 2 || result == 0) -1 else result
}
}🔑 Takeaways
- Pattern: 多源 BFS — 從所有源點同時擴展找最遠距離
- Key trick: 多源 BFS 是找「每個點到最近源點距離」的經典做法；DP 雙向掃描是替代方案