腐烂的橘子 图解题解

这道题到底在问什么

grid

2,1,1 / 1,1,0 / 0,1,1

输出

4

最优解：一步一步想明白

1. 3转折：普通 BFS 从一个点出发，这里腐烂是同时从多处发生的。所以把所有初始烂橘子一次性放进队列，再用 for _ in range(len(q)) 一次只处理「这一层」，每推进一整层就过去一分钟。开始前先数一遍好橘子 fresh，最后用它判断是否全烂。
2. 4fresh=6, 分钟=0扫一遍：好橘子 fresh=6（绿），唯一的烂橘子 (0,0)（橙）入队，灰色 (1,2)、(2,0) 是空格。计时 0 分钟。
3. 5分钟=0，看四邻本层只有 (0,0)。看它上下左右：上、左越界，右 (0,1) 和下 (1,0) 是好橘子，要被传染。计时还停在 0——等这层邻居真的烂了，才算过去 1 分钟。
4. 6fresh=4(0,1)、(1,0) 变烂（高亮），fresh 6→4，它们入队等下一层。第 1 分钟结束。
5. 7fresh=2本层 (0,1)、(1,0) 同时传染各自的好邻居：(0,2) 和 (1,1) 变烂，fresh 4→2。
6. 80 不传播负例：(1,1) 想往右传到 (1,2)、(1,0) 想往下传到 (2,0)，但这两格是空格 0，腐烂传不过去，直接跳过。只有值为 1 的好橘子才会被传染。
7. 9fresh=1第 3 分钟：(1,1) 往下把 (2,1) 传染变烂，fresh 2→1。
8. 10fresh=0第 4 分钟：(2,1) 把最后的 (2,2) 传染，fresh 1→0。
9. 11fresh=0 → 4 分钟队列空了，检查 fresh==0：全烂！返回 4 分钟。若还剩好橘子（被空格隔绝），就返回 -1。
10. 14以后你遇到「同时从多处扩散、求最短时间/距离」的题，就用多源 BFS：01 矩阵、地图分析都是它。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from collections import deque
class Solution:
    def orangesRotting(self, grid):
        m, n = len(grid), len(grid[0])
        q = deque(); fresh = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 2: q.append((r, c))   # 所有烂橘子入队
                elif grid[r][c] == 1: fresh += 1
        minutes = 0
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        while q and fresh:
            for _ in range(len(q)):          # 按层(分钟)处理
                r, c = q.popleft()
                for dr, dc in dirs:
                    nr, nc = r+dr, c+dc
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                        grid[nr][nc] = 2; fresh -= 1; q.append((nr, nc))
            minutes += 1
        return minutes if fresh == 0 else -1

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), fresh = 0;
        queue<pair<int,int>> q;
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 2) q.push({r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        int minutes = 0, dr[] = {1,-1,0,0}, dc[] = {0,0,1,-1};
        while (!q.empty() && fresh) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto cell = q.front(); q.pop();
                for (int d = 0; d < 4; d++) {
                    int nr = cell.first+dr[d], nc = cell.second+dc[d];
                    if (nr>=0 && nr<m && nc>=0 && nc<n && grid[nr][nc]==1) {
                        grid[nr][nc] = 2; fresh--; q.push({nr, nc});
                    }
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }
};

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length, fresh = 0;
        Queue<int[]> q = new LinkedList<>();
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 2) q.offer(new int[]{r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        int minutes = 0;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty() && fresh > 0) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int[] cur = q.poll();
                for (int[] d : dirs) {
                    int nr = cur[0]+d[0], nc = cur[1]+d[1];
                    if (nr>=0 && nr<m && nc>=0 && nc<n && grid[nr][nc]==1) {
                        grid[nr][nc] = 2; fresh--; q.offer(new int[]{nr, nc});
                    }
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }
}

# 「同时从多个源扩散、求最短时间/距离」都套
q = deque(所有起点); seen = set(所有起点)
level = 0
while q:
    for _ in range(len(q)):        # 锁定"这一层"
        x = q.popleft()
        for y in 邻居(x):
            if y not in seen: seen.add(y); q.append(y)
    level += 1                     # 一层 = 一个时间单位

复杂度

面试官可能追问