994 腐烂的橘子

一、题目

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

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

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

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

二、题解

思路：多源 BFS（水波蔓延）

你可以把腐烂的过程想象成“水滴落入平静的水面泛起涟漪”或者“多个感染源同时向外扩散”。因为所有初始就腐烂的橘子会在同一分钟开始向外传染，所以我们需要把它们放在同一批次处理。

  1. 统计与初始化（入队）：首先遍历整个网格。把所有一开始就腐烂的橘子坐标放入队列中，把它们当作第 0 分钟的“感染源”。同时，数一下有多少个新鲜橘子（freshCount）。
  2. 按层级扩散（BFS）：只要队列不为空，且还有新鲜橘子，就开始循环。每一次循环代表“过去了一分钟”。
    • 获取当前队列的长度 size，这代表当前这一分钟内具备传染能力的橘子数量。
    • 依次把这 size 个橘子出队，去感染它们上下左右的邻居。
    • 如果邻居是新鲜橘子，就让它腐烂（变成 2），新鲜橘子总数减 1，并把这个新腐烂的橘子坐标放入队列，作为下一分钟的感染源。
  3. 结束与检查：当扩散停止后，检查 freshCount。如果还是大于 0，说明有些橘子永远感染不到（比如被空位隔开了），返回 -1。如果等于 0，返回记录的分钟数。
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;

        // 1. 初始化：寻找所有的腐烂源放入队列，并统计新鲜橘子的数量
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) {
                    // 腐烂的橘子坐标入队
                    queue.offer(new int[]{r, c});
                } else if (grid[r][c] == 1) {
                    // 统计新鲜橘子数量
                    freshCount++;
                }
            }
        }

        // 如果一开始就没有新鲜橘子，直接返回 0 分钟
        if (freshCount == 0) return 0;

        int minutes = 0;
        // 上下左右四个方向的偏移量
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // 2. 多源 BFS：按“分钟”（层级）向外扩散
        while (!queue.isEmpty() && freshCount > 0) {
            // 当前队列的大小，就是这一分钟内可以向外传染的腐烂橘子数量
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int r = current[0];
                int c = current[1];

                // 向四个方向感染
                for (int[] dir : directions) {
                    int nr = r + dir[0];
                    int nc = c + dir[1];

                    // 检查边界，并且只有遇到新鲜橘子（1）才感染
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2; // 将其变为腐烂橘子
                        freshCount--;     // 新鲜橘子数量减少
                        queue.offer(new int[]{nr, nc}); // 新腐烂的橘子入队，成为下一分钟的感染源
                    }
                }
            }
            // 处理完这一批次（即这一分钟的蔓延），时间增加
            minutes++;
        }

        // 3. 检查是否还有剩余的新鲜橘子
        return freshCount == 0 ? minutes : -1;
    }
}

时间复杂度：O(m×n)O(m \times n)

空间复杂度：O(m×n)O(m \times n)

评论