542. 01 Matrix

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.

Analysis:

BFS, instead of BFS from 1s, but BFS from 0s. So 1 BFS can do the job. 

Solution:

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return matrix;
        
        int m = matrix.length;
        int n = matrix[0].length;
        Queue<int[]> queue = new LinkedList<>();

        int[][] dis = new int[m][n];
        
        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 {
                    dis[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        
        int[][] dir = new int[][]{{0, 1},{0, -1},{1, 0},{-1, 0}};
        
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] d: dir) {
                int x = cur[0] + d[0];
                int y = cur[1] + d[1];
                if (0 <= x && x < m && 0 <=y && y < n
                   && dis[x][y] == Integer.MAX_VALUE) {
                    dis[x][y] = dis[cur[0]][cur[1]] + 1;
                    queue.offer(new int[]{x, y});
                }
            }
        }
        
        return dis;
    }
}