994. Rotting Oranges

Medium

Description

給定一個 m x n 的網格，0 代表空格，1 代表新鮮橘子，2 代表腐爛橘子。每分鐘腐爛橘子會感染四方向相鄰的新鮮橘子。回傳所有橘子都腐爛所需的最少分鐘數，若不可能則回傳 -1。

Example:

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

Intuition#

多源 BFS：所有腐爛橘子同時作為起點，一層一層往外擴散，層數就是答案。

這是典型的多源最短路徑問題，BFS 的每一層代表一分鐘
先將所有腐爛橘子加入佇列作為初始源頭
記錄新鮮橘子數量，BFS 結束後若仍有新鮮橘子則回傳 -1

Approaches#

1: 暴力模擬#

概念: 每分鐘掃描整個網格，找出新被感染的橘子，重複直到穩定
時間複雜度: O((m * n)^2)
空間複雜度: O(1)

class Solution {
    fun orangesRotting(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        var minutes = 0
        var changed = true

        while (changed) {
            changed = false
            val toRot = mutableListOf<IntArray>()
            for (i in 0 until m) {
                for (j in 0 until n) {
                    if (grid[i][j] == 2) {
                        for ((dr, dc) in listOf(0 to 1, 0 to -1, 1 to 0, -1 to 0)) {
                            val ni = i + dr
                            val nj = j + dc
                            if (ni in 0 until m && nj in 0 until n && grid[ni][nj] == 1) {
                                toRot.add(intArrayOf(ni, nj))
                                changed = true
                            }
                        }
                    }
                }
            }
            for ((r, c) in toRot) grid[r][c] = 2
            if (changed) minutes++
        }

        for (i in 0 until m)
            for (j in 0 until n)
                if (grid[i][j] == 1) return -1
        return minutes
    }
}

⭐2: 多源 BFS#

概念: 所有腐爛橘子同時入隊，BFS 逐層擴散，層數即為所需時間
時間複雜度: O(m * n)
空間複雜度: O(m * n)

class Solution {
    fun orangesRotting(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val queue: ArrayDeque<Int> = ArrayDeque()
        var fresh = 0
        val dirs = intArrayOf(0, 1, 0, -1, 0)

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid[i][j] == 2) queue.add(i * n + j)
                else if (grid[i][j] == 1) fresh++
            }
        }

        var minutes = 0
        while (queue.isNotEmpty() && fresh > 0) {
            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 && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2
                        fresh--
                        queue.add(nr * n + nc)
                    }
                }
            }
            minutes++
        }

        return if (fresh == 0) minutes else -1
    }
}

🔑 Takeaways#

Pattern: 多源 BFS – 多個起點同時擴散，求最短時間/距離
關鍵技巧: 用 fresh 計數器判斷是否所有橘子都已腐爛；BFS 層級計數 = 時間單位