01矩阵

542. 01 矩阵

难度中等508

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

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

示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• mat 中至少有一个 0

BFS

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int [][]road ={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int m = mat.length;
        int n = mat[0].length;

        int [][] ans = new int[m][n];
        boolean [][]vis = new boolean[m][n];
        Queue<Node> queue  = new LinkedList<>();

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j]==0){
                    vis[i][j] = true;
                    queue.offer(new Node(i,j));
                }
            }
        }

        while(!queue.isEmpty()){
            Node node = queue.poll();
            int x = node.x;
            int y = node.y;
            for(int i=0;i<4;i++){
                int tempx = x+road[i][0];
                int tempy = y+road[i][1];
                if(tempx<0||tempy<0||tempx>=m||tempy>=n||vis[tempx][tempy]){
                    continue;
                }
                queue.offer(new Node(tempx,tempy));
                ans[tempx][tempy] = ans[x][y]+1;
                vis[tempx][tempy] = true;
            }
        }

        return ans;
    }

    class Node{
        int x;
        int y;
        public Node(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}

赏

谢谢你请我吃糖果

微信