542. 01 Matrix

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:

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

DFS failed with TLE; I was insane to try dfs first …; think it twice next time.

This bfs is a competition of all zeros, zeros capture closest ones in turn.

public int[][] updateMatrix(int[][] matrix) {
    int[][] result = new int[matrix.length][matrix[0].length];
    for(int i = 0; i < result.length; i++)
        for(int j = 0; j < result[0].length; j++)
            if(matrix[i][j] == 1)
                result[i][j] = Integer.MAX_VALUE;

    int[] xs = {0,0,-1,1}, ys = {1,-1,0,0};
    Queue<int[]> q = new LinkedList<>();
    for(int i = 0; i < result.length; i++)
        for(int j = 0; j< result[0].length; j++)
            if(matrix[i][j] == 0) // start from all zeros, then step 1, step 2...
                q.offer(new int[]{i,j});

    while(!q.isEmpty()) {
        int[] curr = q.poll();
        for(int k = 0; k < 4; k++) {
            int x = curr[0] + xs[k], y = curr[1] + ys[k];
            if(x < 0 || y < 0 || x >= result.length || y >= result[0].length) continue;
            if(result[x][y] > result[curr[0]][curr[1]]+1) {
                result[x][y] = result[curr[0]][curr[1]]+1;
                q.offer(new int[] {x,y});
            }
        }
    }
    return result;

}

Two pass dp

public int[][] updateMatrix(int[][] matrix) {
    int MAX = matrix.length + matrix[0].length;
    int[][] dp = new int[matrix.length][matrix[0].length];
    for(int i = 0; i < dp.length; i++) {
        for(int j = 0; j < dp[0].length; j++) {
            if(matrix[i][j] == 1){
                int top = i-1 >= 0 ? dp[i-1][j] : MAX;
                int left = j-1 >= 0 ? dp[i][j-1] : MAX;
                dp[i][j] = Math.min(left, top)+1;
            }
        }
    }
    for(int i = dp.length-1; i >= 0; i--) {
        for(int j = dp[0].length-1; j >= 0; j--) {
            if(matrix[i][j] == 1) {
                int right = j+1 < dp[0].length ? dp[i][j+1] : MAX;
                int bottom = i+1 < dp.length ? dp[i+1][j] : MAX;
                dp[i][j] = Math.min(dp[i][j], Math.min(right, bottom)+1);
            }
        }
    }
    return dp;
}