542. 01 Matrix

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

 

Example 1:


Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
Example 2:


Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
 

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
There is at least one 0 in mat.

#Solution

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        Queue<int[]> queue=new LinkedList<>();
    for(int i=0;i<matrix.length;i++){
      for(int j=0;j<matrix[0].length;j++){
        if(matrix[i][j]==0)
          queue.add(new int[]{i,j});
        else
          matrix[i][j]=-1;
      }
    }
    int[][] dirs= {{0,1},{-1,0},{1,0},{0,-1}};

    int length=0;
    while(!queue.isEmpty()){
      int size=queue.size();
      length++;
      while(size-->0){
        int[] cell=queue.poll();
        for(int[] dir:dirs){
          int r=cell[0]+dir[0];
          int c=cell[1]+dir[1];
          if(r<0 || c<0 || r==matrix.length || c==matrix[0].length || matrix[r][c]!=-1)                                   continue;
          matrix[r][c]=length;
          queue.add(new int[]{r,c});
        }
      }
    }
    return matrix;
    }
}