給定一個
m x n的網格，0代表空格，1代表新鮮橘子，2代表腐爛橘子。每分鐘腐爛橘子會感染四方向相鄰的新鮮橘子。回傳所有橘子都腐爛所需的最少分鐘數，若不可能則回傳-1。
Example:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4
Intuition
TIP
多源 BFS：所有腐爛橘子同時作為起點，一層一層往外擴散，層數就是答案。
- 這是典型的多源最短路徑問題，BFS 的每一層代表一分鐘
- 先將所有腐爛橘子加入佇列作為初始源頭
- 記錄新鮮橘子數量，BFS 結束後若仍有新鮮橘子則回傳
-1
Approaches
1. Brute-Force Simulation — O((m * n)^2) / O(1)
- Idea: 每分鐘掃描整個網格，找出新被感染的橘子，重複直到穩定
- Time:
O((m * n)^2) - Space:
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. Multi-Source BFS — O(m * n) / O(m * n)
- Idea: 所有腐爛橘子同時入隊，BFS 逐層擴散，層數即為所需時間
- Time:
O(m * n) - Space:
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 — 多個起點同時擴散，求最短時間/距離
- Key trick: 用
fresh計數器判斷是否所有橘子都已腐爛；BFS 層級計數 = 時間單位