2._腐烂的🍊

• 3.1

  • 腐烂的才入队列，且在 while 循环中，一次性取出腐烂橘子，并向每个腐烂橘子四周扩散
  • 新鲜橘子用 fresh 计数，time 遍历初始为 -1，且为 fresh 为 0 时立刻返回 0；以解决边界问题

• 2.12

  • 记忆点 1：q 存坐标用 int【】泛型
  • fresh 和 time 不一样
  • 声明方向数组不需要 new
  • 每次进入 while 循环 time++，fresh 发现时++

• 1.30

  • 与岛屿相同，只不过这里取到烂橘子后加入队列开始由方向数组传播（而不是 dfs 传播）
  • 需要注意时间的初始值为-1

• 11.14

  • 一般,就是BFS,因为是一轮一轮的,每轮取出腐烂橘子遍历(数组方向法),然后腐烂掉记录,加入队列即可
  • 向队列加入新坐标:new int[]{i,j}
  • 在队列取出时,需要在方向数组的遍历下(向下移动)开始判断
  • 判断与岛屿数量相反 !!判断在里且为新鲜橘子,腐烂 ,而岛屿数量是判边界外且为水时,淹掉.本质相同

class Solution {
    public int orangesRotting(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        int fresh = 0;//新鲜橘子记数
        //初始化队列+统计新鲜橘子数量
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==2) q.offer(new int[]{i,j});
                if(grid[i][j]==1) fresh++;
            }
        }
        if(fresh==0) return 0;
        int minutes = -1;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        //BFS扩散
        while(!q.isEmpty()){
            int size = q.size();
            minutes++;
            for(int k=0;k<size;k++){
                int[] cur = q.poll();
                int x = cur[0],y=cur[1];
                for(int[] d:dirs){
                    int nx = x+d[0],ny = y+d[1];
                    if(nx>=0&&ny>=0&&nx<m&&ny<n&&grid[nx][ny]==1){
                        grid[nx][ny]=2;
                        fresh--;
                        q.offer(new int[]{nx,ny});
                    }
                }
            }
        }
        return fresh==0?minutes:-1;
    }
}

• 初始化队列
• 记录腐烂与新鲜橘子,腐烂橘子的坐标插入队列
• 制造方向数组
• 开始bfs:取出一个腐烂橘子开始扩散,岛屿判断,新鲜减一,腐烂加入队列