Question

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.

Example 1:
Input:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2:
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

Note:

  1. The number of elements of the given matrix will not exceed 10,000.
  2. There are at least one 0 in the given matrix.
  3. The cells are adjacent in only four directions: up, down, left and right.

Solution

  • Method 1: bfs find from all 1s 
    class Solution {      
    public int[][] updateMatrix(int[][] matrix) {
        int height = matrix.length, width = matrix[0].length;
        int[][] result = new int[height][width];
        for(int i = 0; i < height; i++)
            for(int j = 0; j < width; j++)
                result[i][j] = 10000;
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if(matrix[i][j] == 0){
                    result[i][j] = 0;
                    continue;   
                }
                LinkedList<int[]> queue = new LinkedList<>();
                int dist = -1;
                queue.add(new int[]{i, j});
                boolean[][] visited = new boolean[height][width];
                visited[i][j] = true;
                boolean found = false;
                while(!queue.isEmpty() && !found){
                    ++dist;
                    int size = queue.size();
                    for(int s = 0; s < size; s++){
                        int[] cur = queue.poll();
                        int tempRow = 0, tempCol = 0;
                        for(int d = 0; d < 4; d++){
                            tempRow = dir[d][0] + cur[0];
                            tempCol = dir[d][1] + cur[1];
                            if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && !visited[tempRow][tempCol]){
                                if(matrix[tempRow][tempCol] == 0 || result[tempRow][tempCol] != 10000){
                                    result[i][j] = Math.min(result[i][j], matrix[tempRow][tempCol] == 0 ? dist + 1: result[tempRow][tempCol] + dist + 1);
                                    found = true;
                                }
                                visited[tempRow][tempCol] = true;
                                queue.add(new int[]{tempRow, tempCol});
                            }
                        }
                        if(found) break;
                    }
                }
            }
        }
        return result;
    }
}
  • Method 2: bfs find from all zeros 
    class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int height = matrix.length, width = matrix[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[height][width];
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if(matrix[i][j] == 0){
                    visited[i][j] = true;
                    queue.offer(new int[]{i, j});
                }
            }
        }
        while(!queue.isEmpty()){
            int[] p = queue.poll();
            int tempRow = 0, tempCol = 0;
            for(int d = 0; d < 4; d++){
                tempRow = dir[d][0] + p[0];
                tempCol = dir[d][1] + p[1];
                if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && !visited[tempRow][tempCol]){
                    matrix[tempRow][tempCol] = matrix[p[0]][p[1]] + 1;
                    visited[tempRow][tempCol] = true;
                    queue.add(new int[]{tempRow, tempCol});
                }
            }
        }
        return matrix;
    }
}
  • Method 3: DP 
    class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int height = matrix.length, width = matrix[0].length;
        int[][] result = new int[height][width];
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if(matrix[i][j] != 0){
                    result[i][j] = 10000;
                    if(i > 0) result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
                    if(j > 0) result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
                }
            }
        }
        for(int i = height - 1; i >= 0; i--){
            for(int j = width - 1; j >= 0; j--){
                if(i < height - 1) result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
                if(j < width - 1) result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
            }
        }
        return result;
    }
}