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

蔚落 2023-01-12 11:59 91阅读 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 条评论，91人围观）

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

相关阅读

相关【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 赞/ 40 阅读

相关多源bfs

这是 LeetCode 上的「1162. 地图分析」，难度为「中等」。与「单源最短路」不同，「多源最短路」问题是求从「多个源点」到达「一个/多个汇点」的最短路径。在实

左手的ㄟ右手/ 2024年03月22日 23:18/ 0 赞/ 44 阅读

相关 BFS常见模板题（初学BFS推荐，附例题由浅入深）

BFS类题目：主要考查对广度搜索的理解。 BFS相比于暴力枚举来说效率更高。 BFS只要将范围矩阵扫一次即可得出答案。本文通过队列来实现求解，当然也可以用其他方

喜欢ヅ旅行/ 2023年07月12日 14:14/ 0 赞/ 57 阅读

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

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

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

相关面试题 01.08. 零矩阵

[面试题 01.08. 零矩阵][01.08.] [https://leetcode-cn.com/problems/zero-matrix-lcci/submissions

谁践踏了优雅/ 2022年11月25日 13:13/ 0 赞/ 131 阅读

相关矩阵距离（多源BFS）

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

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

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

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

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

相关 542 01 矩阵（多源bfs）

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

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

相关 [leetcode]-542 01 Matrix

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

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

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

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

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