542.01矩阵

题目链接：542. 01 Matrix

开始我的思路是找每个1然后广度优先遍历直到找到0的距离，发现这种方法难以实现且晦涩。看了大神的题解才明白，使用广度优先搜索需要从0开始，一层一层往外寻找。

_ _ _ _         _ 1 _ _         2 1 2 _         2 1 2 3         2 1 2 3
_ 0 _ _   ==>   1 0 1 _   ==>   1 0 1 2   ==>   1 0 1 2   ==>   1 0 1 2
_ _ _ _         _ 1 _ _         2 1 2 _         2 1 2 3         2 1 2 3
_ _ _ _         _ _ _ _         _ 2 _ _         3 2 3 _         3 2 3 4

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/01-matrix/solution/01ju-zhen-by-leetcode-solution/

我们把全部的0入队，并且把原来的1置为-1（说明没有被访问过），然后出队，如果周围有-1，则距离就是出队的元素的数值+1

代码：

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int N = matrix.length;
        int M = matrix[0].length;
        Deque<int[]> deque = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrix[i][j] == 0)  //把所有0入队
                    deque.offer(new int[]{i, j});
                if (matrix[i][j] == 1) 
                    matrix[i][j] = -1;  //把1都置为-1,表示没有访问过
            }
        }
        int[] xPos = new int[]{0, 0, 1, -1};
        int[] yPos = new int[]{-1, 1, 0, 0};
        while (!deque.isEmpty()) {
            int[] pos = deque.poll();
            for (int i = 0; i < 4; i++) {
                int x = pos[0] + xPos[i];
                int y = pos[1] + yPos[i];
                if (x >= 0 && x < N && y >= 0 && y < M && matrix[x][y] == -1) {
                    //每个出队元素只访问其上下左右四个方向
                    matrix[x][y] = matrix[pos[0]][pos[1]] + 1;
                    deque.offer(new int[]{x, y});   //改变了后入队,检查其上下左右
                }
            }
        }

        return matrix;
    }
}