leetcode 542. 01 Matrix（01矩阵）-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 542. 01 Matrix（01矩阵）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

leetcode 542. 01 Matrix（01矩阵）,leetcode,leetcode,矩阵

矩阵中只有0，1值，返回每个cell到最近的0的距离。

思路：

0元素到它自己的距离是0，
只需考虑1到最近的0是多少距离。

BFS.

先把元素1处的距离更新为无穷大。
0的位置装入queue。
从每个0出发，走上下左右4个方向，遇到0不需要处理，遇到1，距离为当前距离+1.

如果当前距离+1 比下一位置的距离小，
把下一位置的距离更新为当前距离+1，同时说明从下一位置出发的距离都需要更新，装入queue.文章来源地址https://www.toymoban.com/news/detail-663634.html

    public int[][] updateMatrix(int[][] mat) {
        int rows = mat.length;
        int cols = mat[0].length;

        Queue<int[]> queue = new LinkedList<>();
        int max = rows * cols;

        //初始化，0处加入queue, 1处设为最大值
        for(int r = 0; r < rows; r++) {
            for(int c = 0; c < cols; c++) {
                if(mat[r][c] == 0) queue.offer(new int[]{r,c});
                else mat[r][c] = max;
            }
        }

        int[] direc = new int[]{-1,0,1,0,-1};

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            for(int i = 0; i < 4; i++) {
                int nextR = cur[0] + direc[i];
                int nextC = cur[1] + direc[i+1];
                if(nextR >= 0 && nextR < rows && nextC >= 0 && nextC < cols && mat[cur[0]][cur[1]]+1 < mat[nextR][nextC]){
                    mat[nextR][nextC] = mat[cur[0]][cur[1]]+1;
                    queue.offer(new int[]{nextR, nextC});
                }
            }
        }
        return mat;
    }