LeetCode 994、腐烂的橘子

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

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

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

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

示例 1：

img

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

示例 2：

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

示例 3：

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

二、题目解析

三、参考代码

1、Java 代码

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

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

        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++;
                }
            }
        }

        if (freshNum == 0) {
            return 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--;
                    }
                }
            }
        }

        return freshNum > 0 ? -1 : level - 1;
    }
}

**2、**C++ 代码

class Solution {
private:
    static constexpr int DIRECTIONS[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

public:
    int orangesRotting(vector<vector<int>>& grid) {
        int level = 0, freshNum = 0, x = grid.size(), y = grid[0].size();
        queue<pair<int, int>> q;
        vector<vector<int>> checkList(x, vector<int>(y, 0));

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

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

        while (!q.empty()) {
            int qSize = q.size();
            level++;
            for (int k = 0; k < qSize; k++) {
                auto curr = q.front();
                q.pop();
                int i = curr.first, j = curr.second;
                for (auto 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.push({nextI, nextJ});
                        checkList[nextI][nextJ] = 1;
                        freshNum--;
                    }
                }
            }
        }

        return freshNum > 0 ? -1 : level - 1;
    }
};

3、Python 代码

# 题目：LC994. 腐烂的橘子
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：多源BFS
# 代码看不懂的地方，请直接在群上提问


D = [(0,1), (1,0), (-1,0), (0,-1)]

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        # 初始化答案变量、新鲜橘子数量、网格长宽
        level, fresh_num, x, y = 0, 0, len(grid), len(grid[0])    
        # 初始化队列，维护BFS过程
        q = deque()                               
        # 初始化二维列表，用于BFS过程中的检查  
        checkList = [[0] * y for _ in range(x)]   
        # 第一次遍历整个二维网格，找到所有初始腐烂的橘子，统计新鲜橘子的个数
        for i in range(x):
            for j in range(y):
                # 找到初始腐烂的橘子
                if grid[i][j] == 2:
                    # 将腐烂的橘子放入队列中
                    q.append((i, j))
                    # 同时修改二维检查列表的对应元素为1  
                    checkList[i][j] = 1
                # 找到初始新鲜的橘子
                elif  grid[i][j] == 1:
                    # 统计新鲜橘子的数目
                    fresh_num += 1

        # 若新鲜橘子数量为0，则直接返回0
        if fresh_num == 0:
            return 0

        # 进行BFS搜索的循环，套用BFS万能模板
        while len(q) > 0:
            # 获得当前队列长度，为当前层搜索的个数   
            qSize = len(q)
            # 搜索层数+1
            level += 1
            # 循环qSize次，出队qSize次
            for _ in range(qSize):
                # 出队
                i, j = q.popleft()

                # 考虑上下左右四个方向的其他位置
                for dx, dy in D:
                    nxt_i, nxt_j = i+dx, j+dy

                    # 满足三个条件
                    if 0 <= nxt_i < x and 0 <= nxt_j < y and checkList[nxt_i][nxt_j] == 0 and grid[nxt_i][nxt_j] == 1:
                        # 新鲜橘子入队，标记检查，新鲜橘子数目-1
                        q.append((nxt_i, nxt_j))
                        checkList[nxt_i][nxt_j] = 1
                        fresh_num -= 1
                        

        # 若BFS结束，仍存在新鲜橘子，说明有些橘子无法腐烂，返回-1
        # 否则返回level-1，为腐烂所有新鲜橘子所需的时间
        return -1 if fresh_num > 0 else level-1