【LeetCode Hot 100】994. 腐烂的橘子：一文搞懂多源 BFS

大家好，欢迎来到算法学习专栏。今天我们要聊的是力扣（LeetCode）Hot 100 中的一道经典题目——994. 腐烂的橘子。这道题是广度优先搜索（BFS）的经典应用，特别是多源 BFS的典型代表。

腐烂的橘子

📝 题目描述

在给定的 m x n 网格中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

规则： 每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。

要求： 返回直到单元格中没有新鲜橘子为止，所必须经过的最小分钟数。如果不可能实现（即最终还有新鲜橘子无法被腐烂），则返回 -1。

---

💡 思路分析

看到“每分钟向四周扩散”，我们很容易联想到波的扩散过程。这种一层一层向外扩展的特性，正是**广度优先搜索（BFS）**的拿手好戏。

再看看这道题的题目要求：返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。翻译一下，实际上就是求腐烂橘子到所有新鲜橘子的最短路径。那么这道题使用 BFS，应该是毫无疑问的了。

什么是多源 BFS？

通常的 BFS 是从一个起点开始扩散。但在这道题中，初始状态下可能有多个腐烂的橘子（多个源头）。怎么办呢？
很简单，我们只需要在 BFS 开始前，把所有初始状态为腐烂的橘子的坐标同时放入队列中。让它们作为第一层一起向外扩散，这样就能保证所有新鲜橘子被感染的时间是最短且正确的。

核心解题步骤：

1. 统计与初始化： 遍历整个网格，统计新鲜橘子的数量，并将所有腐烂橘子的坐标放入队列。
2. 分层扩散（按分钟计时）：
   • 只要队列不为空，且还有新鲜橘子存在，就进行循环。
   • 每次循环代表过了 1 分钟。我们需要记录当前队列的长度，只处理当前这一层的橘子（即这一分钟内会传染别人的橘子）。
   • 对当前层的每个橘子，检查其上、下、左、右四个方向。如果是新鲜橘子，将其变成腐烂橘子，新鲜橘子数量减一，并把这个新腐烂的橘子加入队列，等待下一分钟继续传染。
   • 当前层处理完后，时间 +1。
3. 判断结果：
   • 队列为空时，如果新鲜橘子数量为 0，返回消耗的时间。
   • 如果新鲜橘子数量仍大于 0，说明有些橘子被隔离了，无法被传染，返回 -1。

(注：视频讲解中UP主口误说返回1，实际力扣原题要求返回 -1，大家在写代码时要注意哦)

---

代码实现

根据上面的思路，我们可以写出如下代码（以 Python 为例）：

class Solution {
    // 上下左右四个方向
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int orangesRotting(int[][] grid) {
        int time = 0;        // 经过的分钟数
        int fresh = 0;       // 剩余新鲜橘子数量
        Queue<int[]> q = new ArrayDeque<>();  // 存放腐烂橘子坐标的队列

        // 1. 初始化：统计新鲜橘子数量，将所有腐烂橘子入队
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                int temp = grid[i][j];
                if (temp == 1) {
                    fresh++;
                } else if (temp == 2) {
                    q.offer(new int[]{i, j});
                }
            }
        }

        // 没有新鲜橘子，直接返回 0
        if (fresh == 0) {
            return 0;
        }

        // 2. 多源 BFS：每轮扩散一层，对应一分钟
        while (!q.isEmpty() && fresh > 0) {
            int size = q.size();
            time++;
            // 处理当前层的所有腐烂橘子
            while (size-- > 0) {
                int[] temp = q.poll();
                int row = temp[0];
                int col = temp[1];
                // 向四个方向感染相邻的新鲜橘子
                for (int j = 0; j < 4; j++) {
                    int newRow = row + DIRECTIONS[j][0];
                    int newCol = col + DIRECTIONS[j][1];
                    // 越界或非新鲜橘子，跳过
                    if (newRow < 0 || newRow >= grid.length
                        || newCol < 0 || newCol >= grid[0].length
                        || grid[newRow][newCol] != 1) {
                        continue;
                    }
                    fresh--;
                    grid[newRow][newCol] = 2;            // 标记为腐烂
                    q.offer(new int[]{newRow, newCol});   // 入队，下一轮继续扩散
                }
            }
        }

        // 3. 若新鲜橘子已全部腐烂返回时间，否则返回 -1
        return fresh == 0 ? time : -1;
    }
}

复杂度分析

• 时间复杂度：$O(m\times n)$。我们需要遍历整个网格一次来寻找初始状态，BFS 过程中每个单元格最多被访问一次。
• 空间复杂度：$O(m\times n)$。最坏情况下，网格中全是腐烂的橘子，它们会同时被放入队列中。

---

🎯 总结

“腐烂的橘子”是一道非常经典的 BFS 模板题。掌握这道题的关键在于理解多源 BFS 的思想：将多个起始点同时放入队列，并利用分层遍历的特性来记录时间步数。

只要遇到“最短时间、最少步数、层层扩散”之类的关键词，第一时间想到广度优先搜索准没错！