算法入门第九天

542. 01 矩阵

这一次了解的是bsf的常见使用

542这一题比较巧妙的一个点是可以直接修改原始数组的值，既能保证避免重复访问走过的节点，最后也符合输入新的数组的要求。

/**
 *
 542. 01 矩阵
 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

 两个相邻元素间的距离为 1 。



 示例 1：



 输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
 输出：[[0,0,0],[0,1,0],[0,0,0]]
 示例 2：



 输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
 输出：[[0,0,0],[0,1,0],[1,2,1]]


 提示：

 m == mat.length
 n == mat[i].length
 1 <= m, n <= 10^4
 1 <= m * n <= 10^4
 mat[i][j] is either 0 or 1.
 mat 中至少有一个 0


 * @author zeroheart
 *
 */
public class Question542 {
   public int[][] updateMatrix(int[][] mat) {

      LinkedList<int[]> queue = new LinkedList<>();
      int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

      int m = mat.length;
      int n = mat[0].length;
      for(int i = 0; i<m; i++){
         for(int j = 0; j<n; j++){
            if(mat[i][j] == 0){
               queue.add(new int[]{i, j});
            }else{
               mat[i][j] = -1;
            }
         }
      }

      while (!queue.isEmpty()){
         int[] poll = queue.poll();
         int x = poll[0];
         int y = poll[1];

         // 四个方向
         for(int i = 0; i<4; i++){
            int newx = dx[i]+x;
            int newy = dy[i]+y;

            if(newx<m && newx>=0 && newy<n && newy>=0 && mat[newx][newy]==-1){
               mat[newx][newy] = mat[x][y] + 1;
               queue.add(new int[]{newx, newy});
            }

         }
      }

      return mat;
   }

   public static void main(String[] args) {
   }

}

994. 腐烂的橘子

烂橘子和上面类似，不过这个返回的是扩散的轮次，这个要注意，所谓一轮，是所有的都要遍历一次，不是一个个来。另外一直在修改queue的值，需要把size提出来才行。

/**
 *
 994. 腐烂的橘子
 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

 值 0 代表空单元格；
 值 1 代表新鲜橘子；
 值 2 代表腐烂的橘子。
 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

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



 示例 1：



 输入：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 。


 提示：

 m == grid.length
 n == grid[i].length
 1 <= m, n <= 10
 grid[i][j] 仅为 0、1 或 2


 * @author zeroheart
 *
 */
public class Question994 {
   public static int orangesRotting(int[][] grid) {
      int m = grid.length;
      int n = grid[0].length;

      int count = 0;
      Queue<int[]> queue = new LinkedList();
      for(int i =0; i<m; i++){
         for(int j = 0; j<n; j++){
            if(grid[i][j] == 2){
               queue.add(new int[]{i, j});
            }else if(grid[i][j] == 1){
               count++;
            }
         }
      }

      int minute = 0;
      int[] dx = {-1, 1, 0, 0};
      int[] dy = {0, 0, -1, 1};
      while (count>0 && !queue.isEmpty()){
         minute++;

         int size = queue.size();// 下面有修改，这里要提出来
         for(int z = 0; z<size;z++){
            // 这才叫一轮
            int[] q = queue.poll();
            int x = q[0];
            int y = q[1];

            for(int i = 0; i<4; i++){
               int newx = x + dx[i];
               int newy = y + dy[i];

               if(newx>=  0 && newx<m && newy>=0 && newy<n && grid[newx][newy] == 1){
                  grid[newx][newy] = 2;
                  queue.add(new int[]{newx, newy});
                  count--;
               }
            }
         }

      }

      return count > 0 ? -1 : minute;
   }

   public static void main(String[] args) {
      System.out.println(orangesRotting(new int[][]{{2,1,1},{1,1,1},{0,1,2}}));
   }

}