542. 01 Matrix

542. 01 Matrix

Medium

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
BFS, 把所有的0放入queue中，用额外数组记录visited情况
O(m*n) time and space

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] rt = new int[m][n];
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> que = new LinkedList<>();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) que.add(new int[]{i,j});
            }
        }
        
        int dis = 0;
        while (!que.isEmpty()) {
            for (int size = que.size(); size > 0; size--) {
                int[] top = que.poll();
                int r = top[0], c = top[1];
                
                if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c]) continue;
                visited[r][c] = true;
                rt[r][c] = dis;
                que.add(new int[]{r - 1, c});
                que.add(new int[]{r + 1, c});
                que.add(new int[]{r, c + 1});
                que.add(new int[]{r, c - 1});
            }
            
            dis++;
        }
        
        return rt;
    }
}

Solution #2， DP，每个点有上下左右4个方向可以选择，如果符合条件，选每个方向路径都增加1。那我们先从matrix左上走到右下，再右下到左上。这样4个方向全部检查过
跟#1一样的复杂度
ref: https://leetcode.com/problems/01-matrix/discuss/101039/Java-33ms-solution-with-two-sweeps-in-O(n)