286. Walls and Gates

Medium
Description

給定一個 m x n 的網格，-1 代表牆壁，0 代表門，INF（2147483647）代表空房間。將每個空房間填入到最近的門的距離。若無法到達任何門，保持 INF。

Example:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]] Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Intuition#

多源 BFS：從所有門（值為 0）同時出發，逐層擴散填入距離值。

  • 從每個空房間出發找最近的門會造成大量重複計算
  • 反向思考：從所有門同時出發 BFS，每擴散一層距離加一
  • 和 994. Rotting Oranges 是同一個多源 BFS 模式

Approaches#

1: 從每個房間 BFS（暴力）#

  • 概念: 對每個空房間做一次 BFS 找到最近的門
  • 時間複雜度: O((m * n)^2)
  • 空間複雜度: O(m * n)
class Solution {
    fun wallsAndGates(rooms: Array<IntArray>) {
        val m = rooms.size
        val n = rooms[0].size
        val dirs = intArrayOf(0, 1, 0, -1, 0)

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (rooms[i][j] == Int.MAX_VALUE) {
                    val queue: ArrayDeque<Int> = ArrayDeque()
                    val visited = Array(m) { BooleanArray(n) }
                    queue.add(i * n + j)
                    visited[i][j] = true
                    var dist = 0
                    var found = false
                    while (queue.isNotEmpty() && !found) {
                        dist++
                        val size = queue.size
                        repeat(size) {
                            val cur = queue.removeFirst()
                            val r = cur / n
                            val c = cur % n
                            for (d in 0 until 4) {
                                val nr = r + dirs[d]
                                val nc = c + dirs[d + 1]
                                if (nr in 0 until m && nc in 0 until n && !visited[nr][nc] && rooms[nr][nc] != -1) {
                                    if (rooms[nr][nc] == 0) {
                                        rooms[i][j] = dist
                                        found = true
                                        return@repeat
                                    }
                                    visited[nr][nc] = true
                                    queue.add(nr * n + nc)
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

⭐2: 多源 BFS（從所有門出發）#

  • 概念: 將所有門加入佇列，BFS 逐層擴散，第一次到達的空房間距離即為最短距離
  • 時間複雜度: O(m * n)
  • 空間複雜度: O(m * n)
class Solution {
    fun wallsAndGates(rooms: Array<IntArray>) {
        val m = rooms.size
        val n = rooms[0].size
        val queue: ArrayDeque<Int> = ArrayDeque()
        val dirs = intArrayOf(0, 1, 0, -1, 0)

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (rooms[i][j] == 0) queue.add(i * n + j)
            }
        }

        while (queue.isNotEmpty()) {
            val cur = queue.removeFirst()
            val r = cur / n
            val c = cur % n
            for (d in 0 until 4) {
                val nr = r + dirs[d]
                val nc = c + dirs[d + 1]
                if (nr in 0 until m && nc in 0 until n && rooms[nr][nc] == Int.MAX_VALUE) {
                    rooms[nr][nc] = rooms[r][c] + 1
                    queue.add(nr * n + nc)
                }
            }
        }
    }
}

🔑 Takeaways#

  • Pattern: 多源 BFS – 從目標反向擴散，與 994. Rotting Oranges 相同模式
  • 關鍵技巧: rooms[nr][nc] == Int.MAX_VALUE 同時充當「未訪問」和「是空房間」的判斷，不需額外 visited 陣列