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.

这道题要首先至少得观察出一个规律，就比如说Eg2里面得input matrix[1][1]位置的1，它离最近的0的距离就是它上下左右几个点中离0距离最近的点离0的距离加上一。如果观察到这个关键点，那就可以用BFS将题目迎刃而解了。

首先我们遍历整个矩阵，将等于0的点放入queue里面。将不等于0的点初始值设为Integer.MAX_VALUE. 然后开始从queue里面poll元素出来，每poll 出来一个，就遍历其上下左右四个点。首先判断是不是inbound, 或者是不是小于被取出queue的点的值。如果小于等于取出来的点的值，则不需要更新；如果大于被取出来的点的值，就更新为取出来的点的值 + 1,并且要加到queue里面。

class Solution {
    class ResultType{
        public int x;
        public int y;
        public ResultType(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public int r;
    public int c;
    Queue<ResultType> queue;
    public int[][] updateMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return null;
        }
        r = matrix.length;
        c = matrix[0].length; 
        queue = new LinkedList<>();
        for (int i = 0; i < r; i++){
            for (int j = 0; j < c; j++){
                if (matrix[i][j] == 0){
                    queue.offer(new ResultType(i, j));
                } else {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        while (!queue.isEmpty()){
            ResultType curt = queue.poll();
            int x = curt.x;
            int y = curt.y;
            BFS(matrix, queue, x, y, x - 1, y);
            BFS(matrix, queue, x, y, x + 1, y);
            BFS(matrix, queue, x, y, x, y + 1);
            BFS(matrix, queue, x, y, x, y - 1);
        }
        return matrix;
    }
    
    private void BFS(int[][] matrix, Queue<ResultType> queue, int x, int y, int i, int j){
        if (i < 0 || i >= r || j < 0 || j >= c || matrix[x][y] >= matrix[i][j]){
            return;
        }    
        matrix[i][j] = matrix[x][y] + 1;
        queue.offer(new ResultType(i,j));
    }
}