LeetCode 994 腐烂的橘子Rotting Oranges题解多源 BFS 与逐层时间模拟【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇指南以 LeetCode 994「腐烂的橘子」为实战载体系统讲解**多源 BFSMulti-source BFS**在二维网格上的应用如何从所有腐烂橘子同时出发逐层扩散、如何用队列记录每一分钟的感染边界以及不借助队列、仅靠网格标记模拟时间的等价写法。读完你将掌握多源 BFS 的层序计时技巧、新鲜橘子计数法判断不可达情形并能对照本仓库 12 种语言的实现见 python/0994-rotting-oranges.py、java/0994-rotting-oranges.java、go/0994-rotting-oranges.go 等写出可直接运行的解答。前置知识动手解这道题之前需要先熟悉以下四个基础点广度优先搜索BFS逐层遍历的核心算法本题用每一层代表一个时间单位是统计腐烂分钟数的基础多源 BFS不是从单一源点出发而是把多个初始源点所有腐烂橘子同时放入队列一起扩散这是本题的关键思想队列Queue数据结构BFS 过程中按 FIFO 顺序处理单元格保证先腐烂的橘子先扩散二维网格遍历借助方向向量上、下、左、右在矩阵中移动访问相邻单元格。仓库中的 hints/rotting-fruit.md 还给出了额外提示DFS 不适合此题因为它按深度深挖而非逐层展开而本题需要判断每一秒哪些橘子腐烂天然契合逐层遍历的 BFS。1. 基于队列的多源 BFS推荐解法思路直觉这是一道典型的多源 BFS问题。所有腐烂橘子值为2在同一时刻开始向相邻的新鲜橘子值为1传播腐烂。BFS 的每一层恰好代表1 分钟只要某个新鲜橘子被访问到它就在下一分钟变为腐烂。核心要点从所有腐烂橘子一起开始 BFS多源同时入队预先统计新鲜橘子总数每腐烂一个就减一每处理完一整层当前队列中全部节点才让时间加 1结束时若仍有新鲜橘子未腐烂被空单元格0隔离答案为-1。算法步骤初始化队列将网格中所有值为2的腐烂橘子坐标入队遍历网格统计新鲜橘子值为1的总数fresh当队列非空且仍有新鲜橘子时循环记录当前队列长度length即本层要处理的橘子数依次弹出这length个腐烂橘子检查其 4 个邻居若邻居在边界内且为新鲜橘子1将其改为2fresh减 1并入队本层处理完毕后time加 1这一分钟结束若fresh变为0返回time否则返回-1存在永远无法腐烂的橘子。多语言实现class Solution: def orangesRotting(self, grid: List[List[int]]) - int: q collections.deque() fresh 0 time 0 for r in range(len(grid)): for c in range(len(grid[0])): if grid[r][c] 1: fresh 1 if grid[r][c] 2: q.append((r, c)) directions [[0, 1], [0, -1], [1, 0], [-1, 0]] while fresh 0 and q: length len(q) for i in range(length): r, c q.popleft() for dr, dc in directions: row, col r dr, c dc if (row in range(len(grid)) and col in range(len(grid[0])) and grid[row][col] 1 ): grid[row][col] 2 q.append((row, col)) fresh - 1 time 1 return time if fresh 0 else -1public class Solution { public int orangesRotting(int[][] grid) { Queueint[] q new ArrayDeque(); int fresh 0; int time 0; for (int r 0; r grid.length; r) { for (int c 0; c grid[0].length; c) { if (grid[r][c] 1) fresh; if (grid[r][c] 2) q.offer(new int[]{r, c}); } } int[][] directions {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; while (fresh 0 !q.isEmpty()) { int length q.size(); for (int i 0; i length; i) { int[] curr q.poll(); for (int[] dir : directions) { int row curr[0] dir[0], col curr[1] dir[1]; if (row 0 row grid.length col 0 col grid[0].length grid[row][col] 1) { grid[row][col] 2; q.offer(new int[]{row, col}); fresh--; } } } time; } return fresh 0 ? time : -1; } }class Solution { public: int orangesRotting(vectorvectorint grid) { queuepairint, int q; int fresh 0; int time 0; for (int r 0; r grid.size(); r) { for (int c 0; c grid[0].size(); c) { if (grid[r][c] 1) fresh; if (grid[r][c] 2) q.push({r, c}); } } vectorpairint, int directions {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; while (fresh 0 !q.empty()) { int length q.size(); for (int i 0; i length; i) { auto curr q.front(); q.pop(); for (const auto dir : directions) { int row curr.first dir.first; int col curr.second dir.second; if (row 0 row grid.size() col 0 col grid[0].size() grid[row][col] 1) { grid[row][col] 2; q.push({row, col}); fresh--; } } } time; } return fresh 0 ? time : -1; } };class Solution { /** * param {number[][]} grid * return {number} */ orangesRotting(grid) { const q []; let fresh 0; let time 0; for (let r 0; r grid.length; r) { for (let c 0; c grid[0].length; c) { if (grid[r][c] 1) fresh; if (grid[r][c] 2) q.push([r, c]); } } const directions [[0, 1], [0, -1], [1, 0], [-1, 0]]; while (fresh 0 q.length 0) { const length q.length; for (let i 0; i length; i) { const [currR, currC] q.shift(); for (const [dr, dc] of directions) { const row currR dr, col currC dc; if (row 0 row grid.length col 0 col grid[0].length grid[row][col] 1) { grid[row][col] 2; q.push([row, col]); fresh--; } } } time; } return fresh 0 ? time : -1; } }public class Solution { public int OrangesRotting(int[][] grid) { Queueint[] q new Queueint[](); int fresh 0; int time 0; for (int r 0; r grid.Length; r) { for (int c 0; c grid[0].Length; c) { if (grid[r][c] 1) fresh; if (grid[r][c] 2) q.Enqueue(new int[] { r, c }); } } int[][] directions { new int[] { 0, 1 }, new int[] { 0, -1 }, new int[] { 1, 0 }, new int[] { -1, 0 } }; while (fresh 0 q.Count 0) { int length q.Count; for (int i 0; i length; i) { int[] curr q.Dequeue(); foreach (int[] dir in directions) { int row curr[0] dir[0], col curr[1] dir[1]; if (row 0 row grid.Length col 0 col grid[0].Length grid[row][col] 1) { grid[row][col] 2; q.Enqueue(new int[] { row, col }); fresh--; } } } time; } return fresh 0 ? time : -1; } }type Pair struct { row, col int } func orangesRotting(grid [][]int) int { rows, cols : len(grid), len(grid[0]) queue : make([]Pair, 0) fresh : 0 time : 0 for r : 0; r rows; r { for c : 0; c cols; c { if grid[r][c] 1 { fresh } if grid[r][c] 2 { queue append(queue, Pair{r, c}) } } } directions : [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}} for fresh 0 len(queue) 0 { length : len(queue) for i : 0; i length; i { current : queue[0] queue queue[1:] for _, dir : range directions { newRow : current.row dir[0] newCol : current.col dir[1] if newRow 0 newRow rows newCol 0 newCol cols grid[newRow][newCol] 1 { grid[newRow][newCol] 2 queue append(queue, Pair{newRow, newCol}) fresh-- } } } time } if fresh 0 { return time } return -1 }class Solution { data class Pair(val row: Int, val col: Int) fun orangesRotting(grid: ArrayIntArray): Int { val rows grid.size val cols grid[0].size val queue ArrayDequePair() var fresh 0 var time 0 for (r in 0 until rows) { for (c in 0 until cols) { if (grid[r][c] 1) fresh if (grid[r][c] 2) queue.addLast(Pair(r, c)) } } val directions arrayOf( intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0) ) while (fresh 0 queue.isNotEmpty()) { val length queue.size repeat(length) { val current queue.removeFirst() for (dir in directions) { val newRow current.row dir[0] val newCol current.col dir[1] if (newRow in 0 until rows newCol in 0 until cols grid[newRow][newCol] 1) { grid[newRow][newCol] 2 queue.addLast(Pair(newRow, newCol)) fresh-- } } } time } return if (fresh 0) time else -1 } }class Solution { func orangesRotting(_ grid: [[Int]]) - Int { var grid grid var queue Deque(Int, Int)() var fresh 0 var time 0 let ROWS grid.count let COLS grid[0].count for r in 0..ROWS { for c in 0..COLS { if grid[r][c] 1 { fresh 1 } if grid[r][c] 2 { queue.append((r, c)) } } } let directions [[0, 1], [0, -1], [1, 0], [-1, 0]] while fresh 0 !queue.isEmpty { let length queue.count for _ in 0..length { let (r, c) queue.popFirst()! for dir in directions { let row r dir[0], col c dir[1] if row 0 row ROWS col 0 col COLS grid[row][col] 1 { grid[row][col] 2 queue.append((row, col)) fresh - 1 } } } time 1 } return fresh 0 ? time : -1 } }impl Solution { pub fn oranges_rotting(mut grid: VecVeci32) - i32 { let rows grid.len(); let cols grid[0].len(); let mut queue VecDeque::new(); let mut fresh 0; let mut time 0; for r in 0..rows { for c in 0..cols { if grid[r][c] 1 { fresh 1; } if grid[r][c] 2 { queue.push_back((r as i32, c as i32)); } } } let directions [(0, 1), (0, -1), (1, 0), (-1, 0)]; while fresh 0 !queue.is_empty() { let length queue.len(); for _ in 0..length { let (r, c) queue.pop_front().unwrap(); for (dr, dc) in directions { let row r dr; let col c dc; if row 0 row rows as i32 col 0 col cols as i32 grid[row as usize][col as usize] 1 { grid[row as usize][col as usize] 2; queue.push_back((row, col)); fresh - 1; } } } time 1; } if fresh 0 { time } else { -1 } } }时间与空间复杂度时间复杂度$O(m * n)$空间复杂度$O(m * n)$其中 $m$ 为网格行数$n$ 为网格列数。复杂度来源每个单元格最多入队一次腐烂后不会再次处理时间上只需扫描一遍网格加上一次完整 BFS空间上队列在最坏情况下网格全为腐烂橘子可容纳全部 $m \times n$ 个单元格。仓库源码印证本仓库各语言实现与上文算法完全一致可直接对照阅读python/0994-rotting-oranges.pycollections.deque()作为队列row in range(len(grid))完成边界检查java/0994-rotting-oranges.java用LinkedList做队列dirs四方向数组循环条件!queue.isEmpty() fresh ! 0go/0994-rotting-oranges.go用切片模拟队列q q[1:]出队并通过ROW、COL常量下标访问坐标csharp/0994-rotting-oranges.cs、kotlin/0994-rotting-oranges.kt、swift/0994-rotting-oranges.swift、typescript/0994-rotting-oranges.ts、javascript/0994-rotting-oranges.js、cpp/0994-rotting-oranges.cpp 结构相同。2. 不借助队列的 BFS网格标记法思路直觉这一版仍然是按层 BFS只是不再使用队列而是通过网格标记来模拟分钟的推进。把外层循环的每一次迭代看作1 分钟值为2的单元格代表这一分钟开始时已经腐烂的橘子在这一分钟里它们感染的新鲜邻居先被临时标记为3表示下一分钟才会腐烂整张网格扫描完成后把所有3 → 2转换为下一分钟做准备。为什么用3这个中间状态为了防止刚腐烂的橘子在同一个分钟内再次扩散——否则会把时间计算得比真实更快一个橘子在同一分钟里连续感染两圈邻居相当于多跳了一次。如果在某一分钟里没有任何新鲜橘子被标记为3但fresh仍然大于 0说明腐烂已经无法继续传播新鲜橘子被空单元格隔离直接返回-1。算法步骤统计新鲜橘子值为1总数fresh当fresh 0时循环设flag false记录这一分钟是否腐烂了橘子扫描每个单元格若值为2检查 4 个邻居遇到值为1的邻居就标记为3、fresh减 1、置flag true若flag为false说明一分钟内没有任何进展返回-1再次扫描网格把所有3转换为2提交下一层time加 1当fresh 0时返回time。多语言实现class Solution: def orangesRotting(self, grid: List[List[int]]) - int: ROWS, COLS len(grid), len(grid[0]) fresh 0 time 0 for r in range(ROWS): for c in range(COLS): if grid[r][c] 1: fresh 1 directions [[0, 1], [0, -1], [1, 0], [-1, 0]] while fresh 0: flag False for r in range(ROWS): for c in range(COLS): if grid[r][c] 2: for dr, dc in directions: row, col r dr, c dc if (row in range(ROWS) and col in range(COLS) and grid[row][col] 1): grid[row][col] 3 fresh - 1 flag True if not flag: return -1 for r in range(ROWS): for c in range(COLS): if grid[r][c] 3: grid[r][c] 2 time 1 return timepublic class Solution { public int orangesRotting(int[][] grid) { int ROWS grid.length, COLS grid[0].length; int fresh 0, time 0; for (int r 0; r ROWS; r) { for (int c 0; c COLS; c) { if (grid[r][c] 1) fresh; } } int[][] directions {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; while (fresh 0) { boolean flag false; for (int r 0; r ROWS; r) { for (int c 0; c COLS; c) { if (grid[r][c] 2) { for (int[] d : directions) { int row r d[0], col c d[1]; if (row 0 col 0 row ROWS col COLS grid[row][col] 1) { grid[row][col] 3; fresh--; flag true; } } } } } if (!flag) return -1; for (int r 0; r ROWS; r) { for (int c 0; c COLS; c) { if (grid[r][c] 3) grid[r][c] 2; } } time; } return time; } }class Solution { public: int orangesRotting(vectorvectorint grid) { int ROWS grid.size(), COLS grid[0].size(); int fresh 0, time 0; for (int r 0; r ROWS; r) { for (int c 0; c COLS; c) { if (grid[r][c] 1) fresh; } } vectorvectorint directions {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; while (fresh 0) { bool flag false; for (int r 0; r ROWS; r) { for (int c 0; c COLS; c) { if (grid[r][c] 2) { for (auto d : directions) { int row r d[0], col c d[1]; if (row 0 col 0 row ROWS col COLS grid[row][col] 1) { grid[row][col] 3; fresh--; flag true; } } } } } if (!flag) return -1; for (int r 0; r ROWS; r) { for (int c 0; c COLS; c) { if (grid[r][c] 3) grid[r][c] 2; } } time; } return time; } };class Solution { /** * param {number[][]} grid * return {number} */ orangesRotting(grid) { let ROWS grid.length, COLS grid[0].length; let fresh 0, time 0; for (let r 0; r ROWS; r) { for (let c 0; c COLS; c) { if (grid[r][c] 1) fresh; } } let directions [[0, 1], [0, -1], [1, 0], [-1, 0]]; while (fresh 0) { let flag false; for (let r 0; r ROWS; r) { for (let c 0; c COLS; c) { if (grid[r][c] 2) { for (let [dr, dc] of directions) { let row r dr, col c dc; if (row 0 col 0 row ROWS col COLS grid[row][col] 1) { grid[row][col] 3; fresh--; flag true; } } } } } if (!flag) return -1; for (let r 0; r ROWS; r) { for (let c 0; c COLS; c) { if (grid[r][c] 3) grid[r][c] 2; } } time; } return time; } }public class Solution { public int OrangesRotting(int[][] grid) { int ROWS grid.Length, COLS grid[0].Length; int fresh 0, time 0; for (int r 0; r ROWS; r) { for (int c 0; c COLS; c) { if (grid[r][c] 1) fresh; } } int[][] directions new int[][] { new int[] {0, 1}, new int[] {0, -1}, new int[] {1, 0}, new int[] {-1, 0} }; while (fresh 0) { bool flag false; for (int r 0; r ROWS; r) { for (int c 0; c COLS; c) { if (grid[r][c] 2) { foreach (var d in directions) { int row r d[0], col c d[1]; if (row 0 col 0 row ROWS col COLS grid[row][col] 1) { grid[row][col] 3; fresh--; flag true; } } } } } if (!flag) return -1; for (int r 0; r ROWS; r) { for (int c 0; c COLS; c) { if (grid[r][c] 3) grid[r][c] 2; } } time; } return time; } }func orangesRotting(grid [][]int) int { rows, cols : len(grid), len(grid[0]) fresh : 0 time : 0 for r : 0; r rows; r { for c : 0; c cols; c { if grid[r][c] 1 { fresh } } } directions : [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}} for fresh 0 { flag : false for r : 0; r rows; r { for c : 0; c cols; c { if grid[r][c] 2 { for _, d : range directions { row, col : rd[0], cd[1] if row 0 row rows col 0 col cols grid[row][col] 1 { grid[row][col] 3 fresh-- flag true } } } } } if !flag { return -1 } for r : 0; r rows; r { for c : 0; c cols; c { if grid[r][c] 3 { grid[r][c] 2 } } } time } return time }class Solution { fun orangesRotting(grid: ArrayIntArray): Int { val rows grid.size val cols grid[0].size var fresh 0 var time 0 for (r in 0 until rows) { for (c in 0 until cols) { if (grid[r][c] 1) fresh } } val directions arrayOf( intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0) ) while (fresh 0) { var flag false for (r in 0 until rows) { for (c in 0 until cols) { if (grid[r][c] 2) { for (d in directions) { val row r d[0] val col c d[1] if (row in 0 until rows col in 0 until cols grid[row][col] 1) { grid[row][col] 3 fresh-- flag true } } } } } if (!flag) return -1 for (r in 0 until rows) { for (c in 0 until cols) { if (grid[r][c] 3) grid[r][c] 2 } } time } return time } }class Solution { func orangesRotting(_ grid: [[Int]]) - Int { var grid grid let ROWS grid.count let COLS grid[0].count var fresh 0 var time 0 for r in 0..ROWS { for c in 0..COLS { if grid[r][c] 1 { fresh 1 } } } let directions [[0, 1], [0, -1], [1, 0], [-1, 0]] while fresh 0 { var flag false for r in 0..ROWS { for c in 0..COLS { if grid[r][c] 2 { for dir in directions { let row r dir[0], col c dir[1] if (row 0 row ROWS col 0 col COLS grid[row][col] 1) { grid[row][col] 3 fresh - 1 flag true } } } } } if !flag { return -1 } for r in 0..ROWS { for c in 0..COLS { if grid[r][c] 3 { grid[r][c] 2 } } } time 1 } return time } }impl Solution { pub fn oranges_rotting(mut grid: VecVeci32) - i32 { let rows grid.len(); let cols grid[0].len(); let mut fresh 0i32; let mut time 0; for r in 0..rows { for c in 0..cols { if grid[r][c] 1 { fresh 1; } } } let directions: [(i32, i32); 4] [(0, 1), (0, -1), (1, 0), (-1, 0)]; while fresh 0 { let mut flag false; for r in 0..rows { for c in 0..cols { if grid[r][c] 2 { for (dr, dc) in directions { let row r as i32 dr; let col c as i32 dc; if row 0 row rows as i32 col 0 col cols as i32 grid[row as usize][col as usize] 1 { grid[row as usize][col as usize] 3; fresh - 1; flag true; } } } } } if !flag { return -1; } for r in 0..rows { for c in 0..cols { if grid[r][c] 3 { grid[r][c] 2; } } } time 1; } time } }时间与空间复杂度时间复杂度$O((m * n) ^ 2)$空间复杂度$O(1)$其中 $m$ 为网格行数$n$ 为网格列数。每模拟一分钟就要完整扫描两遍网格一遍标记3一遍把3转回2最多需要 $m \times n$ 分钟因此时间上界为 $O((m*n)^2)$由于完全复用原网格不申请额外数据结构空间复杂度为 $O(1)$。仓库中的第三种思路时间戳标记法本仓库的 C 实现 c/0994-rotting-oranges.c 提供了网格标记法的变体不再用3 → 2回写而是把腐烂时间直接写进网格值。rotting_process函数每次只处理时间戳等于当前timestamp的格子把新鲜邻居标记为timestamp 1timestamp从2递增直到某分钟没有任何格子被更新结束后若网格中仍残留值为1的橘子则返回-1否则返回timestamp - 2。这种写法同样实现逐层模拟且天然避免了同分钟内二次扩散适合作为理解网格即状态思想的补充阅读。常见陷阱陷阱一只从一个腐烂橘子开始 BFS一个常见错误是只把某一个腐烂橘子例如第一个遇到的2加入队列而不是把所有腐烂橘子同时入队。由于所有腐烂橘子是同一时刻开始扩散的必须先把网格中每个值为2的单元格全部入队再从多个源点同时展开 BFS。只从一个源点出发会得到错误的时间计算结果。陷阱二忘记统计新鲜橘子数量部分解法在初始遍历时没有统计新鲜橘子总数BFS 结束后也无从判断是否所有橘子都已腐烂。如果没有fresh计数就无法发现被空单元格隔离、永远无法腐烂的橘子。正确做法是每腐烂一个橘子就让fresh减 1BFS 结束后若fresh 0则返回-1。陷阱三时间累加位置错误一个隐蔽的 bug 是每处理完一个橘子就加 1 分钟而不是每处理完一整层才加 1 分钟。因为每一层代表一分钟必须在当前层的全部橘子处理完毕后才能让time加 1。实现上要在进入循环时先记录length len(queue)内层循环恰好处理length个元素外层循环结束时再time 1这样才能正确地把 BFS 层数映射为分钟数。小结**多源 BFS队列版**是本题的标准解法所有腐烂橘子同时入队逐层扩散每层计 1 分钟配合fresh计数判断是否全部腐烂时间复杂度 $O(m*n)$网格标记版无需额外队列用中间状态3模拟下一分钟才腐烂时间变为 $O((m*n)^2)$、空间降为 $O(1)$适合在不能申请额外数据结构时使用三种实现的共同核心都是按层计时 边界检查 新鲜计数这一套模板可以无缝迁移到其他多源扩散类问题如地图分析、洪水填充类题目仓库中 python/0994-rotting-oranges.py、java/0994-rotting-oranges.java、go/0994-rotting-oranges.go、c/0994-rotting-oranges.c 及 hints/rotting-fruit.md 提供了可直接运行的完整实现与解题提示可作为刷题与复习的对照材料。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考