542. 01 矩阵(多源BFS模板题)

蔚落 2023-01-12 11:59 119阅读 0赞

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

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

从每个为“0”的坐标开始进行广度优先遍历

class Solution {
    public:
        typedef pair<int,int> PII;
        static const int INF = 2e9;
        int dx[4] = {1,-1,0,0};
        int dy[4] = {0,0,1,-1};
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            int n = matrix.size(),m = matrix[0].size();
            vector<vector<int>> vis(n,vector<int>(m,0)); 
            if(n == 0 && m == 0) return matrix;
            queue<PII> q;
            for(int i = 0; i < n; ++i){
                for(int j = 0;j < m; ++j){
                    if(matrix[i][j] == 0){
                        vis[i][j] = INF;
                        q.push({i,j});
                    }
                }
            }
            int lay = 0;
            while(q.size()){
                int len = q.size();
                while(len--){
                    int nx = q.front().first;
                    int ny = q.front().second;
                    q.pop();
                    matrix[nx][ny] = lay;
                    for(int i = 0; i < 4; ++i){
                        int cx = nx + dx[i],cy = ny + dy[i];
                        if(cx >= 0 && cx < n && cy >= 0 && cy < m && vis[cx][cy] != INF && matrix[cx][cy] != 0){
                            vis[cx][cy] = INF;
                            q.push({cx,cy});
                        }
                    }
                }
                lay++;
            }
            return matrix;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，119人围观）

还没有评论，来说两句吧...

相关阅读

相关【LeetCode】25. 542_01 Matrix · 01矩阵

题目描述英文版描述 Given an m x n binary matrix mat, return the distance of the nearest 0

心已赠人/ 2024年04月01日 13:20/ 0 赞/ 66 阅读

相关 542.01矩阵解析

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

古城微笑少年丶/ 2023年10月11日 17:07/ 0 赞/ 10 阅读

相关 LeetCode_BFS_中等_542.01 矩阵

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个

落日映苍穹つ/ 2023年10月07日 20:47/ 0 赞/ 12 阅读

相关 Java实现 LeetCode 542 01 矩阵（暴力大法，正反便利）

542. 01 矩阵给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1 。示例 1: 输入: 0 0 0

今天药忘吃喽~/ 2023年07月18日 09:09/ 0 赞/ 1 阅读

相关 542. 01 矩阵(多源BFS模板题)

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1 。从每个为“0”的坐标开始进行广度优先遍历 class So

蔚落/ 2023年01月12日 11:59/ 0 赞/ 120 阅读

相关矩阵距离（多源BFS）

题目描述给定一个N行M列的01矩阵A，A\[i\]\[j\] 与 A\[k\]\[l\] 之间的曼哈顿距离定义为： dist(A[i][j],A[k][l])=

蔚落/ 2022年10月26日 12:56/ 0 赞/ 131 阅读

相关 leetcode 542. 01 Matrix | 542. 01 矩阵（图解，广度优先搜索）

题目 [https://leetcode.com/problems/01-matrix/][https_leetcode.com_problems_01-matrix]

妖狐艹你老母/ 2022年09月02日 04:26/ 0 赞/ 143 阅读

相关 542 01 矩阵（多源bfs）

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

╰+哭是因爲堅強的太久メ/ 2022年08月31日 02:22/ 0 赞/ 144 阅读

相关 [leetcode]-542 01 Matrix

![Center][] 基本思路：对每个cell，设与最近0的距离为d，按d=0~nRows+nCols进行对其附近的cell进行搜索，若搜索到0则立即返回当时的d值 d

旧城等待，/ 2022年06月18日 01:07/ 0 赞/ 151 阅读

相关【LeetCode】 542. 01 矩阵动态规划 dp

<table> <tbody> <tr> <td><font>题目</font></td> </tr> </tbody> </table>

怼烎@/ 2021年06月10日 20:38/ 0 赞/ 341 阅读