矩阵

题目描述：力扣

解题思路：

一. 广度优先搜索
思路：
对于 「Tree 的 BFS」 （典型的「单源 BFS」） 大家都已经轻车熟路了：

首先把 root 节点入队，再一层一层无脑遍历就行了。
对于 「图 的 BFS」 （「多源 BFS」） 做法其实也是一样滴～，与 「Tree 的 BFS」的区别注意以下两条就 ok 辣～

Tree 只有 1 个 root，而图可以有多个源点，所以首先需要把多个源点都入队；
Tree 是有向的因此不需要标识是否访问过，而对于无向图来说，必须得标志是否访问过哦！并且为了防止某个节点多次入队，需要在其入队之前就将其设置成已访问！【 看见很多人说自己的 BFS 超时了，坑就在这里哈哈哈
做法：
根据上述思路，本题怎么做就很简单了：

首先把每个源点 00 入队，然后从各个 00 同时开始一圈一圈的向 11 扩散（每个 11 都是被离它最近的 00 扩散到的 ），扩散的时候可以设置 int[][] dist 来记录距离（即扩散的层次）并同时标志是否访问过。对于本题是可以直接修改原数组 int[][] matrix 来记录距离和标志是否访问的，这里要注意先把 matrix 数组中 1 的位置设置成 -1 （设成Integer.MAX_VALUE啦，m * n啦，10000啦都行，只要是个无效的距离值来标志这个位置的 1 没有被访问过就行辣~）
复杂度分析：

每个点入队出队一次，所以时间复杂度：O(n * m)O(n∗m)
虽然我们是直接原地修改的原输入数组来存储结果，但最差的情况下即全都是 00 时，需要把 m * nm∗n 个 00 都入队，因此空间复杂度是 O(n * m)O(n∗m)

作者：sweetiee
链接：https://leetcode-cn.com/problems/01-matrix/solution/2chong-bfs-xiang-jie-dp-bi-xu-miao-dong-by-sweetie/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    //多源BFS
    public int[][] updateMatrix(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] res = new int[row][col];
        boolean [][] isvisited = new boolean[row][col];
        int[][] directions = {
  {-1,0},{1,0},{0,-1},{0,1}};
        Queue<int[]> queue = new LinkedList<>();
        //对于已经是0的，res对应位置赋值为0，遍历数组赋值为true,并将其位置加入到队列中
        for(int i = 0 ; i < row; i++ ){
            for(int j = 0 ; j < col; j++ ){
                if(matrix[i][j]==0){
                    res[i][j]=0;
                    isvisited[i][j] = true;
                    queue.offer(new int[]{i,j});
                }
            }
        }
        while(!queue.isEmpty()){
            int[] start = queue.poll();
            int x = start[0];
            int y = start[1];
            for(int[] direction:directions){
                int new_x = x+direction[0];
                int new_y = y+direction[1];
                if(new_x >= 0 && new_x <row && new_y >= 0 && new_y < col ){
                    if(!isvisited[new_x][new_y] && matrix[new_x][new_y]==1){
                        res[new_x][new_y]=res[x][y]+1;
                        isvisited[new_x][new_y] = true;
                        queue.offer(new int[]{new_x,new_y});
                    }
                }
            }
        }
        return res;
    }

}