LC994. 腐烂的橘子

题目描述

题目解析

题目在说什么

想象你有一个网格，里面放着橘子。有的橘子是新鲜的（用数字1表示），有的已经腐烂了（用数字2表示），还有一些格子是空的（用数字0表示）。 腐烂的橘子会“传染”——每分钟，每个腐烂橘子会把它上下左右四个方向相邻的新鲜橘子也变腐烂。 问题是：需要多少分钟，所有新鲜橘子都会腐烂？ 如果有些新鲜橘子永远无法被传染（比如被空格子隔开了），就返回 -1。如果一开始就没有新鲜橘子，返回 0。

思路是怎么来的

这个问题的核心是“同时传染”，就像病毒扩散一样。我们可以把腐烂橘子想象成“感染源”，每分钟它们会感染周围的邻居。 这种“一层一层往外扩散”的模式，很像广度优先搜索（BFS）。BFS 就像水波一样，从起点开始，先扩散到离起点最近的一圈，再扩散到第二圈……每一圈就是“一分钟”。

但这里有个特别的地方：一开始可能有多个腐烂橘子。比如网格里有两个腐烂橘子，它们会同时开始传染。这叫做多源 BFS——也就是有多个起点，同时往外扩散。

所以思路是： 1. 先找到所有腐烂橘子，把它们作为起点。 2. 然后一层一层地往外扩散，每扩散一层，时间就过去一分钟。 3. 同时记录新鲜橘子还剩多少，如果最后还有新鲜橘子没被感染，就说明不可能全部腐烂，返回 -1。

代码逐步拆解

我们来看参考代码，一行一行解释它在干什么。

private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

• 这定义了四个方向：上、下、左、右。因为腐烂橘子只能感染上下左右相邻的橘子。

int level = 0, freshNum = 0, x = grid.length, y = grid[0].length;
Queue<int[]> q = new LinkedList<>();
int[][] checkList = new int[x][y];

• level：记录当前是第几分钟（从0开始）。
• freshNum：记录新鲜橘子的总数。
• x 和 y：网格的行数和列数。
• q：队列，用来存放当前所有腐烂橘子的坐标。
• checkList：一个和网格一样大的二维数组，用来标记某个位置是否已经被访问过（防止重复处理）。

for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
        if (grid[i][j] == 2) {
            q.offer(new int[]{i, j});
            checkList[i][j] = 1;
        } else if (grid[i][j] == 1) {
            freshNum++;
        }
    }
}

• 遍历整个网格：
• 如果遇到腐烂橘子（值为2），就把它加入队列，并标记为已访问（checkList[i][j] = 1）。
• 如果遇到新鲜橘子（值为1），就把 freshNum 加1。

if (freshNum == 0) {
    return 0;
}

• 如果一开始就没有新鲜橘子，那就不需要时间，直接返回0。

while (!q.isEmpty()) {
    int qSize = q.size();
    level++;
    for (int k = 0; k < qSize; k++) {
        int[] curr = q.poll();
        int i = curr[0], j = curr[1];
        for (int[] dir : DIRECTIONS) {
            int nextI = i + dir[0], nextJ = j + dir[1];
            if (nextI >= 0 && nextI < x && nextJ >= 0 && nextJ < y 
                && checkList[nextI][nextJ] == 0 && grid[nextI][nextJ] == 1) {
                q.offer(new int[]{nextI, nextJ});
                checkList[nextI][nextJ] = 1;
                freshNum--;
            }
        }
    }
}

• 这是 BFS 的核心部分：
• 每次循环，先记录当前队列的大小 qSize，这表示当前这一分钟有多少个腐烂橘子。
• 然后 level++，表示又过了一分钟。