【Leetcode】542.01矩阵

542.01矩阵

题目

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:
输入:
0 0 0
0 1 0
0 0 0

输出:
0 0 0
0 1 0
0 0 0

示例 2:
输入:
0 0 0
0 1 0
1 1 1

输出:
0 0 0
0 1 0
1 2 1

方法（BFS）

对于二叉树的BFS，都是单源BFS。
而对于图的BFS，大多是多源BFS

因为二叉树只有一个根节点，先把根节点入队，再一层层遍历即可。而图可以有许多源点，因此需要先把这些源点都入队，再一层层遍历。

对于本题来说，先将所有的0（源点）入队列，再从0开始一层一层向周围未遍历到的1扩散。最后将矩阵中所有的点都遍历到。

注意：树是有向的，因此无需标记一个节点是否被访问过。而对于无向图来说，为了防止一个节点多次入队，需要在访问它之后将它标记为已访问。（对于本题来说，将其标记为非-1）

算法步骤：

  • 先遍历一遍矩阵，将0出现的位置索引入队列，并将所有的1置为-1，表明这是还没被访问过的1.
  • 用dx和dy两个矩阵来表示向上下左右四个位置的移动
  • 移动到没有访问过的1时，将其入队列，并更新matrix[newX][newY]（本来为-1）为matrix[x][y] + 1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int[][] updateMatrix(int[][] matrix) {
    Queue<int[]> queue = new LinkedList<>();
    int m = matrix.length, n = matrix[0].length;
    //先遍历一次矩阵，将0出现的位置索引入队列
    //并把1的位置设置为-1，表示这是还没被访问的1
    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
                matrix[i][j] = -1;
        }
    }
    int[] dx = new int[]{-1, 1, 0, 0};
    int[] dy = new int[]{0, 0, -1, 1};
    while(!queue.isEmpty()){
        int[] node = queue.poll();
        int x = node[0], y = node[1];
        for(int i = 0; i < 4; i++){
            //newX和newY为附近邻居的位置索引
            int newX = x + dx[i];
            int newY = y + dy[i];
            //如果邻居值为-1，说明它是还没被访问过的1.
            //则这个点到0的距离就可以更新为matrix[x][y] + 1,注意：这步更新完之后这个点就有实际值而不是-1了，相当于被标记了。
            //当遇到被标记过（访问过）的点时，不将其入队列
            if(newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == -1){
                matrix[newX][newY] = matrix[x][y] + 1;
                queue.offer(new int[] {newX, newY});
            }
        }
    }
    return matrix;
}

题目1162. 地图分析和此题目类似

参考