1162. As Far from Land as Possible

Medium
Description

給定一個 n x n 的網格 grid，1 代表陸地、0 代表水域。求水域格子到最近陸地的曼哈頓距離中，最大的那個值。若全是陸地或全是水域，回傳 -1。

Example:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]] Output: 2

Intuition#

多源 BFS – 從所有陸地同時出發，最後被到達的水域格子就是答案。

  • 將所有陸地格子作為 BFS 起點（多源 BFS）
  • 同時向外擴展，每層距離加一
  • 最後一個被訪問到的水域格子的距離就是最大距離

Approaches#

⭐1: 多源 BFS#

  • 概念: 所有陸地同時入隊，BFS 層層擴展，最後一層的距離即為答案
  • 時間複雜度: O(n^2)
  • 空間複雜度: 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: 動態規劃#

  • 概念: 兩次掃描：左上到右下、右下到左上，計算每個格子到最近陸地的距離
  • 時間複雜度: O(n^2)
  • 空間複雜度: 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 – 從所有源點同時擴展找最遠距離
  • 關鍵技巧: 多源 BFS 是找「每個點到最近源點距離」的經典做法；DP 雙向掃描是替代方案