Leetcode--Java--542. 01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

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

多源BFS （多源最短路问题）+ 图论思想

从图论的角度来考虑本题，假设只有一个0，则相当于求每个点到0的距离，可以用bfs从0位置开始向四周扩散，依次距离加一，直到扫描完所有的结点。（设置一个访问数组，访问过的就标记）在1的基础上拓展， 如果是多个0，可以将这些0全部看成一个整体（难以理解的话，也可以想象成有一个超源点，这些0都连接到这个超源点，就可以转化为求每个点到超源点的距离，也即是1的情况），依次从每个0点开始BFS，然后不断入队新的位置，就会依次迭代更新每个位置到0的距离图论的角度考虑，这里队列存的是点的坐标，相邻的点距离固定为1

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int dist[][] = new int[m][n]; //答案数组
        int dx[] = new int[]{0, 1, 0, -1};
        int dy[] = new int[]{1, 0, -1, 0};
        boolean vis[][] = new boolean[m][n];
        Deque q = new linkedList<>();
        //将所有的0源点入队
        for (int i = 0; i < m; i ++ ) {
            for (int j = 0; j < n; j ++ ) {
                if (mat[i][j] == 0) {
                    q.offer(new int[]{i, j});
                    vis[i][j] = true;
                }
            }
        }
        //多源点BFS
        while (!q.isEmpty()) {
            int node[] = q.poll();
            //枚举四周
            for (int d = 0; d < 4; d ++ ) {
                int nx = node[0] + dx[d], ny = node[1] + dy[d];
                //没越界并且没出现过
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny]) {
                    dist[nx][ny] = dist[node[0]][node[1]] + 1;
                    vis[nx][ny] = true;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        return dist;
    }
}