Problem

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.

自己最初思路（bfs - 1找0）

• 对于每一个点1， 使用bfs去找到最近的0点
• 假如有n个点， 时间复杂度O（n ^ 2）
• 因为一个1点可能被多次进入queue， 倘若只有一个0点，这样几乎每个点都需要全图找寻。

正确思路（bfs - 0 找 1）

• 将所有的0点放入queue， 只要（周围的点与0点的距离） >（当前点与零点距离）+ 1, 才更新
• 时间复杂度O（n）, 每个点只会进入queue一次

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

        int m = matrix.length;
        int n = matrix[0].length;

        int[][] res = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                } else {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        int count = 0;
        while (!queue.isEmpty()) {
            count++;
            int[] curt = queue.poll();
            for (int j = 0; j < 4; j++) {
                int[] next = new int[]{curt[0] + dx[j], curt[1] + dy[j]};
                if (next[0] < 0 || next[1] < 0 || next[0] >= m || next[1] >= n || matrix[next[0]][next[1]] <= matrix[curt[0]][curt[1]] + 1) continue;
                queue.offer(next);
                matrix[next[0]][next[1]] = matrix[curt[0]][curt[1]] + 1;
            }

        }    

        return matrix;
    }

正确思路（dfs， but TLE）

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

        int m = matrix.length;
        int n = matrix[0].length;

        int[][] res = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }

       for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    dfs(matrix, i, j);
                }
            }
        }

        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);

    }



    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};

    private void dfs (int[][] matrix, int x, int y) {
        for (int i = 0; i < 4; i++) {
            int r = x + dx[i];
            int c = y + dy[i];

            if (r < 0 || r >= matrix.length || c < 0 || c >= matrix[0].length || matrix[r][c] <= matrix[x][y] + 1) continue;
            matrix[r][c] = matrix[x][y] + 1;
            dfs(matrix, r, c);
        }

    }