994. 腐烂的橘子

力扣题目链接 (opens new window)

题目描述

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

• 0 表示单元格为空；
• 1 表示单元格中有一个新鲜橘子；
• 2 表示单元格中有一个腐烂的橘子。

每分钟，腐烂橘子周围四个方向上相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

示例 1：

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

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的新鲜橘子永远不会腐烂。

示例 3：

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

提示：

• 1 <= m, n <= 10
• grid[i][j] 只能是 0、1 或 2

思路

看到“最少经过多少分钟”，很容易想到 BFS，因为 BFS 按距离一层一层向外扩散。

但本题和普通 BFS 有一点不同：网格里可能一开始就有多个腐烂橘子，它们会在同一分钟同时扩散。

如果从每个腐烂橘子分别做一次 BFS，会有什么问题？同一块区域会被重复搜索，而且很难正确合并各自的时间。

正确做法是：先把所有腐烂橘子一起放进队列，把它们当成 BFS 的第 0 层。 这就是多源 BFS。

同时统计新鲜橘子的数量 fresh：

1. 初始化时，所有值为 2 的位置入队，所有值为 1 的位置计入 fresh；
2. 队列中的当前一层代表同一分钟开始时已经腐烂的橘子；
3. 它们让相邻新鲜橘子腐烂，新腐烂的橘子进入下一层，fresh 减一；
4. 只要本轮确实腐烂了新橘子，分钟数才加一；
5. BFS 结束后，如果 fresh > 0，说明有橘子被空格隔开，返回 -1。

为什么不能每处理一个橘子就让时间加一？因为同一层的所有橘子是在同一分钟同时扩散，时间对应的是 BFS 层数，不是出队次数。

模拟过程

为了把“多源”看清楚，图中使用一个包含两个初始腐烂橘子的网格：

2 1 1 1 2
1 1 0 1 1
0 1 1 1 0

初始化时，左上角和右上角两个腐烂橘子一起进入 Q0。第 1 分钟只处理 Q0 中的两个源点，它们新腐烂的四个位置组成 Q1；第 2 分钟再只处理 Q1，新腐烂的位置组成 Q2。队列就这样按层推进。

图中方括号 [2] 表示当前分钟刚腐烂、即将进入下一层队列的位置。扩散到第 4 层时，最后一个新鲜橘子变腐烂，所以答案是 4。

注意，这不是从两个源点分别做两次 BFS，而是把所有源点放进同一个第 0 层。这样每个格子第一次被访问时的层数，就是它到最近源点的最短距离。

解题代码

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int, int>> rotten;
        int fresh = 0;

        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 2) rotten.push({i, j});
                else if (grid[i][j] == 1) ++fresh;
            }
        }

        int minutes = 0;
        int directions[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

        while (!rotten.empty() && fresh > 0) {
            int size = rotten.size();
            ++minutes; // 当前这一层统一扩散一分钟

            while (size--) {
                auto [x, y] = rotten.front();
                rotten.pop();

                for (auto& direction : directions) {
                    int nextX = x + direction[0];
                    int nextY = y + direction[1];
                    if (nextX < 0 || nextX >= grid.size() ||
                        nextY < 0 || nextY >= grid[0].size() ||
                        grid[nextX][nextY] != 1) {
                        continue;
                    }
                    grid[nextX][nextY] = 2; // 入队时标记，避免重复入队
                    --fresh;
                    rotten.push({nextX, nextY});
                }
            }
        }

        return fresh == 0 ? minutes : -1;
    }
};

复杂度分析

• 时间复杂度：O(m × n)，每个单元格最多入队一次。
• 空间复杂度：O(m × n)，最坏情况下队列保存 O(m × n) 个位置。

其他语言

Python3

from collections import deque

class Solution:
    def orangesRotting(self, grid):
        rows, cols = len(grid), len(grid[0])
        queue, fresh = deque(), 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 2:
                    queue.append((i, j))
                elif grid[i][j] == 1:
                    fresh += 1

        minutes = 0
        while queue and fresh > 0:
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                        grid[nx][ny] = 2
                        fresh -= 1
                        queue.append((nx, ny))
            minutes += 1
        return minutes if fresh == 0 else -1

Java

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new ArrayDeque<>();
        int fresh = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) queue.offer(new int[]{i, j});
                else if (grid[i][j] == 1) fresh++;
            }
        }

        int minutes = 0;
        int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        while (!queue.isEmpty() && fresh > 0) {
            int size = queue.size();
            minutes++;
            while (size-- > 0) {
                int[] current = queue.poll();
                for (int[] direction : directions) {
                    int x = current[0] + direction[0];
                    int y = current[1] + direction[1];
                    if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != 1) continue;
                    grid[x][y] = 2;
                    fresh--;
                    queue.offer(new int[]{x, y});
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
}

Go

func orangesRotting(grid [][]int) int {
    queue, fresh := [][2]int{}, 0
    for i := range grid {
        for j := range grid[0] {
            if grid[i][j] == 2 { queue = append(queue, [2]int{i, j}) }
            if grid[i][j] == 1 { fresh++ }
        }
    }

    minutes := 0
    directions := [][2]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
    for len(queue) > 0 && fresh > 0 {
        size := len(queue)
        minutes++
        for i := 0; i < size; i++ {
            current := queue[0]
            queue = queue[1:]
            for _, direction := range directions {
                x, y := current[0]+direction[0], current[1]+direction[1]
                if x < 0 || x >= len(grid) || y < 0 || y >= len(grid[0]) || grid[x][y] != 1 { continue }
                grid[x][y] = 2
                fresh--
                queue = append(queue, [2]int{x, y})
            }
        }
    }
    if fresh > 0 { return -1 }
    return minutes
}

JS

var orangesRotting = function(grid) {
    const rows = grid.length, cols = grid[0].length;
    const queue = [];
    let fresh = 0, front = 0;

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === 2) queue.push([i, j]);
            else if (grid[i][j] === 1) fresh++;
        }
    }

    let minutes = 0;
    const directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    while (front < queue.length && fresh > 0) {
        const levelEnd = queue.length;
        minutes++;
        while (front < levelEnd) {
            const [x, y] = queue[front++];
            for (const [dx, dy] of directions) {
                const nx = x + dx, ny = y + dy;
                if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || grid[nx][ny] !== 1) continue;
                grid[nx][ny] = 2;
                fresh--;
                queue.push([nx, ny]);
            }
        }
    }
    return fresh === 0 ? minutes : -1;
};

与代码随想录联系

本题是多源 BFS 的典型应用。建议先看广度优先搜索理论基础，理解队列为什么能够保证按距离分层访问。

再对比200.岛屿数量：200 题关心连通分量个数，遇到一个新起点就搜索一次；本题关心所有起点到其他位置的最短时间，所以要把多个起点同时放进一个队列。