📝 题目描述

题目链接：腐烂的橘子

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

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

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

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例：

示例 1：

1
2
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：

1
2
3
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

1
2
3
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] 仅为 0、1 或 2

💡 解题思路

方法一：多源广度优先搜索

这道题本质上是一个层序遍历的问题。腐烂的橘子就像是水波的中心，每一分钟向外扩散一圈。为了避免重复检查已经枯竭的感染源，我们可以使用队列来实现广度优先搜索：

  • 初始化：先遍历一次网格。统计新鲜橘子的数量，方便最后检查是否有残留，并把所有初始的腐烂橘子坐标全部推入队列中，实现初始的多源。
  • BFS 扩散：每一分钟，我们只处理当前队列中存在的橘子，也就是上一分钟刚刚腐烂的橘子。让它们向四周扩散，如果感染了新鲜橘子，就把新鲜橘子变成腐烂，并把这个新腐烂的橘子推入队列，留给下一分钟处理。
  • 终止条件：当队列为空时，扩散结束。如果此时新鲜橘子的数量为 0，说明全部感染，返回花费的分钟数；如果大于 0，说明有橘子永远不会腐烂，返回 -1。

🔧 代码实现

1、多源广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        queue<pair<int, int>> q;
        int freshCount = 0; // 记录新鲜橘子的数量
        
        // 1. 初始化：统计新鲜橘子，将所有初始腐烂的橘子加入队列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    freshCount++;
                } else if (grid[i][j] == 2) {
                    q.push({i, j});
                }
            }
        }
        
        // 如果一开始就没有新鲜橘子，直接返回 0
        if (freshCount == 0) return 0;
        
        int minutes = 0;
        // 定义四个扩散方向：上下左右
        vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // 2. 开始 BFS 扩散
        while (!q.empty()) {
            int currentSize = q.size();
            bool rottedThisMinute = false; // 标记这一分钟是否有橘子被感染
            
            // 将当前队列里这一层的腐烂橘子全部取出，向外扩散一层
            for (int i = 0; i < currentSize; i++) {
                auto [r, c] = q.front();
                q.pop();
                
                // 遍历当前橘子的四个方向
                for (auto& dir : dirs) {
                    int nr = r + dir.first;
                    int nc = c + dir.second;
                    
                    // 如果坐标合法，且是新鲜橘子
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2; // 变成腐烂橘子
                        freshCount--;     // 新鲜橘子总数减一
                        q.push({nr, nc}); // 将新腐烂的橘子加入队列，作为下一轮的感染源
                        rottedThisMinute = true;
                    }
                }
            }
            // 只有在这分钟内确实有橘子腐烂，时间才增加
            if (rottedThisMinute) {
                minutes++;
            }
        }
        
        // 3. 检查是否还有剩余的新鲜橘子
        return freshCount == 0 ? minutes : -1;
    }
};

📊 复杂度分析

1、多源广度优先搜索

  • 时间复杂度：O(m×n)O(m×n)，我们只需要在初始化时遍历一次网格，之后的 BFS 过程中，每个单元格最多只会被推入队列一次、弹出一次并检查其邻居。
  • 空间复杂度：O(m×n)O(m×n)，主要来自于队列的开销。在最坏的情况下（比如网格里全都是腐烂的橘子），队列中最多会存放 m×nm×n 个元素。

🎯 总结

  • 核心思想：从每波感染想到广度优先搜索，进而想到多源广度优先搜索。