01 矩阵

广度优先搜索

思路：

• 对于 「Tree 的 BFS」 （典型的「单源 BFS」）：
  • 首先把 root 节点入队，再一层一层无脑遍历就行了
• 对于 「图 的 BFS」 （「多源 BFS」）
  • 同样将源节点入队，再取出遍历
  • 与 「Tree 的 BFS」的区别注意：
    • Tree 只有 1 个 root，而图可以有多个源点，所以首先需要把多个源点都入队
    • Tree 是有向的因此不需要标识是否访问过，而对于无向图来说，必须得标志是否访问过！为了防止某个节点多次入队

• 做法：

  • 遍历数组

    • 将源点0入队
    • 将1的赋值为 -1
      • 未被访问的节点

  • 遍历队列

    • 对该源点的上下左右一一进行判断
      • 不能越界、等于-1：为被访问
      • 将其值改为源点值 + 1
      • 这个被访问的 -1 节点 入队（防止其四周有未访问的-1节点，并且源点0是服务访问到的），确保节点都被访问

  • 队列空了：都访问了，处理结束

  • class Solution {
        public int[][] updateMatrix(int[][] matrix) {
            // 首先将所有的 0 都入队，并且将 1 的位置设置成 -1，表示该位置是 未被访问过的 1
            Queue<int[]> queue = new LinkedList<>();
            int m = matrix.length, n = matrix[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == 0) {
                        queue.offer(new int[] {i, j});
                    } else {
                        matrix[i][j] = -1;
                    } 
                }
            }
            
            int[] dx = new int[] {-1, 1, 0, 0};
            int[] dy = new int[] {0, 0, -1, 1};
            while (!queue.isEmpty()) {
                int[] point = queue.poll();
                int x = point[0], y = point[1];
                for (int i = 0; i < 4; i++) {
                    int newX = x + dx[i];
                    int newY = y + dy[i];
                    // 如果四邻域的点是 -1，表示这个点是未被访问过的 1
                    // 所以这个点到 0 的距离就可以更新成 matrix[x][y] + 1。
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n 
                            && matrix[newX][newY] == -1) {
                        matrix[newX][newY] = matrix[x][y] + 1;
                        queue.offer(new int[] {newX, newY});
                    }
                }
            }
    
            return matrix;
        }
    }
    

好文：2种BFS，详解DP， 🤷♀️必须秒懂！ - 01 矩阵 - 力扣（LeetCode） (leetcode-cn.com)

二、腐烂的橘子

• 相比上面，思路差不多，但略简单

思路

• 是图的遍历
• 采用广度优先搜索
• 每个源点标记就是 1、2这样的值
  • 1：等待被污染的新鲜橘子
  • 2：已经腐败的橘子：只访问一次，不重复访问的条件

做法

• 遍历数组
  • 统计新鲜橘子数量
  • 将腐败橘子入队
• 记录初始腐败橘子数量
• 遍历队列
  • 每次出一个源节点
  • 将其四个正方向的位置
    • 是新鲜橘子：赋值为2并污染、count减一、入队
  • size减一：属于该批的橘子数量减一
  • 当size 等于 0：
    • 这一批的腐败橘子已访问完
    • 若队列中还有节点：说明这一批腐败橘子有污染到新鲜橘子，则时间增加
    • size更新：下次不同批次进行污染
• 最后count不等于0：存在没被污染的新鲜橘子：返回-1
• 不然返回time：也可称之为污染环数

class Solution {
   public int orangesRotting(int[][] grid) {
       //将所有的腐烂橘子入队
       //值为2入队，统计新鲜橘子数量
       Queue<int[]> queue = new LinkedList<>();
       int n = grid.length;
       int m = grid[0].length;
       int count = 0;
       for(int i = 0; i < n; i++) {
           for(int j = 0; j < m; j++) {
               if(grid[i][j] == 2) {
                   queue.offer(new int[] {i, j});
               } else if(grid[i][j] == 1) {
                   ++count;
               }
           }
       }

       //上、下、左、右四个附近节点
       int[] dx = new int[] {-1, 1, 0, 0};
       int[] dy = new int[] {0, 0, -1, 1};
       //统计污染时间
       int time = 0;
       //统计不同腐败批次的橘子数量
       int size = queue.size();
       while(!queue.isEmpty()) {
           //处理橘子，附近的1赋值为2且入队
           int[] point = queue.poll();
           int x = point[0], y = point[1];
           for(int i = 0; i < 4; i++) {
               int newx = x + dx[i];
               int newy = y + dy[i];
               if(newx >= 0 && newx < n && newy >= 0 && newy < m
                   && grid[newx][newy] == 1) {
                       //不越界（4个正方向之一）、是新鲜的橘子
                       grid[newx][newy] = 2;
                       --count;
                       queue.offer(new int[] {newx, newy});
               }
           }
           //处理时间，橘子腐败是一批开始的，不同批次占据不同的时间段，初始的坏橘子占据第一个分钟
           //初始橘子污染的橘子（第二批）：占据第二个分钟....依次类推
           //每批次有污染新鲜橘子：队列不为空，时间加1
           size--;
           if(size == 0) {
               if(queue.size() > 0) {
                   time++;
               }
               size = queue.size();
           }
       }
       if(count > 0) {
           return -1;
       }
       return time;
   }
}