542. 01 Matrix

Link

Solution

Base on the known status (for the matrix[i][j] has neighbors with zero), to derive the other unknowns.

  public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length;
        if(m == 0) return matrix;
        int n = matrix[0].length;
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 1 && !hasZeroNeighbor(matrix, i, j)){
                    matrix[i][j] = m + n - 2;
                }
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 1){
                    dfs(matrix, i, j, 1);
                }
            }
        }
        return matrix;
    }
    
    
    public void dfs(int[][] matrix, int i, int j, int value){
        int m = matrix.length, n = matrix[0].length;
        if(i >= m || i < 0 || j >= n || j < 0 || matrix[i][j] < value) return;
        
        
        matrix[i][j] = value;
        dfs(matrix, i+1, j,  value+1);
        dfs(matrix, i-1, j,  value+1);        
        dfs(matrix, i, j+1,  value+1);
        dfs(matrix, i, j-1,  value+1);
        
    }
    
    public boolean hasZeroNeighbor(int[][] matrix, int i, int j){
        int m = matrix.length, n = matrix[0].length;
        if(i+1 < m){
            if(matrix[i+1][j] == 0){
                return true;
            }
        }
        if(i-1 >= 0){
            if(matrix[i-1][j] == 0){
                return true;
            }
        }
        if(j+1 < n){
            if(matrix[i][j+1] == 0){
                 return true;
            }
        }
        if(j-1 >= 0){
            if(matrix[i][j-1] == 0){
                 return true;
            }
        }
        return false;
        
    }