52、图论-腐烂的橘子

思路：

思维转化：

第一步先找出所有腐烂的橘子，这些橘子会在上下左右进行感染，然后记录被感染的 橘子，之前感染过的句子不再使用，将新的感染的橘子收集，然后遍历让其上下左右依次感染，没做一次批量感染，时间加1。

直到无法在搜集新的感染橘子的时候，判断感染橘子的总和和橘子的数量是否相等，如果相等返回最小分钟数，如果不相等，说明有些橘子无法被感染，返回-1。

代码如下：

class Solution {
   public int orangesRotting(int[][] grid) {
    // 如果网格为空或者行或列的长度为0，直接返回0，因为没有橘子。
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }
    
    int num = 0; // 新鲜橘子的数量
    Queue<int[]> queue = new LinkedList<>(); // 用于BFS的队列
    int N = grid.length; // 网格的行数
    int M = grid[0].length; // 网格的列数
    
    // 遍历整个网格
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            // 如果找到一个腐烂的橘子，就将它的位置加入队列
            if (grid[i][j] == 2) {
                int[] position = {i, j};
                queue.add(position);
            }
            // 如果找到一个新鲜的橘子，新鲜橘子的数量加一
            if (grid[i][j] == 1) {
                num++;
            }
        }
    }
    
    // 如果没有新鲜橘子，直接返回0，因为没有橘子需要腐烂
    if (num == 0) {
        return 0;
    }
    
    int count = 0; // 记录所需分钟数
    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 四个可能的移动方向（上下左右）
    
    // 当队列不为空，并且还有新鲜的橘子时，进行BFS
    while (!queue.isEmpty() && num > 0) {
        int size = queue.size(); // 当前队列的大小，代表这一分钟可以腐烂的橘子数量
        for (int i = 0; i < size; i++) {
            int[] point = queue.poll(); // 取出一个腐烂的橘子
            // 遍历四个方向
            for (int[] direction : directions) {
                int x = point[0] + direction[0];
                int y = point[1] + direction[1];
                // 如果相邻的橘子是新鲜的，它就会腐烂
                if (x >= 0 && y >= 0 && x < N && y < M && grid[x][y] == 1) {
                    grid[x][y] = 2; // 标记为腐烂
                    queue.add(new int[]{x, y}); // 将新腐烂的橘子加入队列
                    num--; // 新鲜橘子的数量减少
                }
            }
        }
        count++; // 每完成一轮BFS，时间增加一分钟
    }
    
    // 如果没有新鲜橘子剩余，返回所需的时间，否则返回-1表示有橘子永远不会腐烂
    return num == 0 ? count : -1;
}
}