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 1: DFS: Assigned a large value to all the positions with value 1 and don't have 0 neighbors. Start dfs search from positions whose value is 1.

    public int[][] updateMatrix(int[][] matrix) {
        if(matrix.length==0) return matrix;

        for(int i = 0; i<matrix.length; i++)
            for(int j = 0; j<matrix[0].length; j++)
                if(matrix[i][j]==1&&!hasNeiberZero(i, j,matrix)) 
                    matrix[i][j] = matrix.length+matrix[0].length+1;

        for(int i = 0; i<matrix.length; i++)
            for(int j = 0; j<matrix[0].length; j++)
                if(matrix[i][j]==1)
                    dfs(matrix, i, j, -1);

        return matrix;
    }
    private void dfs(int[][] matrix, int x, int y, int val){
        if(x<0||y<0||y>=matrix[0].length||x>=matrix.length||matrix[x][y]<=val)
            return;

        if(val>0) matrix[x][y] = val;

        dfs(matrix, x+1, y, matrix[x][y]+1);
        dfs(matrix, x-1, y, matrix[x][y]+1);
        dfs(matrix, x, y+1, matrix[x][y]+1);
        dfs(matrix, x, y-1, matrix[x][y]+1);

    }
    private boolean hasNeiberZero(int x, int y, int[][] matrix){
        if(x>0&&matrix[x-1][y]==0) return true;
        if(x<matrix.length-1&&matrix[x+1][y]==0) return true;
        if(y>0&&matrix[x][y-1]==0) return true;
        if(y<matrix[0].length-1&&matrix[x][y+1]==0) return true;

        return false;
    }

or:

    public void DFS(int[][] matrix, int row, int col){
        int[][] direction = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};

        for(int[] d : direction){
            int newRow = row + d[0], newCol = col + d[1];
            if(newRow < 0 || newRow >= matrix.length || newCol < 0 || newCol >= matrix[0].length)   continue;
            //相邻的格子的值大于当前格子值+1时，要更新
            if(matrix[newRow][newCol] > matrix[row][col] + 1){
                matrix[newRow][newCol] = matrix[row][col] + 1;
                DFS(matrix, newRow, newCol);
            }
        }
    }

wrong answer:

    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};
    public int[][] updateMatrix(int[][] A) {
        if(A == null || A.length == 0 || A[0] == null || A[0].length == 0){
            return A;
        }
        int m = A.length, n = A[0].length;
        int[][] distance = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(distance, A, i, j);
            }
        }
        return distance;
    }
    private int dfs(int[][] distance, int[][] A, int x, int y) {
        //不能distance[x][y] > 0就返回，因为有可能这不是最小值，还需要更新
        if (distance[x][y] > 0 || A[x][y] == 0) {
            return distance[x][y];
        }
        distance[x][y] = Integer.MAX_VALUE;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= A.length || ny < 0 || ny >= A[0].length) {
                continue;
            }
            int temp = distance[x][y];
            distance[x][y] = Integer.MAX_VALUE; //置为MAX_VALUE以免stack overflow
            int neighbor = dfs(distance, A, nx, ny);
            if (neighbor != Integer.MAX_VALUE) {
                distance[x][y] = Math.min(temp, neighbor + 1);
            } else {
                //还原
                distance[x][y] = temp;
            }

        }
        return distance[x][y];
    }

Solution 2: 扫2次，第一次正序，根据左值和上值更新当前；第二次反序，根据右值和下值更新当前

public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
        List<List<Integer>> answer = new LinkedList();
        if(matrix.size() == 0) return answer;
        int[][] array = new int[matrix.size()][matrix.get(0).size()];
        int i = 0, j = 0;
        for(List<Integer> list : matrix) {
            for(Integer x : list) {
                if(x == 0) {
                    array[i][j] = 0;
                }
                else {
                    int left = Integer.MAX_VALUE - 1, top = Integer.MAX_VALUE - 1;
                    if(i - 1 >= 0) top = array[i - 1][j];
                    if(j - 1 >= 0) left = array[i][j - 1];
                    array[i][j] = Math.min(Integer.MAX_VALUE - 1, Math.min(top, left) + 1);
                }
                j++;
            }
            j = 0;
            i++;
        }
        for(int k = array.length - 1; k >= 0; k--) {
            for(int m = array[0].length - 1; m >= 0; m--) {
                if(array[k][m] != 0 && array[k][m] != 1) {
                    int down = Integer.MAX_VALUE - 1, right = Integer.MAX_VALUE - 1;
                    if(k + 1 < array.length) down = array[k + 1][m];
                    if(m + 1 < array[0].length) right = array[k][m + 1];
                    array[k][m] = Math.min(array[k][m], Math.min(down, right) + 1);
                }
            }
        }
        for(int[] l : array) {
            List<Integer> tmp = new LinkedList();
            for(int n : l) {
                tmp.add(n);
            }
            answer.add(tmp);
        }
        return answer;
    }