【LeetCode542】01矩阵(BFS)

简介: (1)其实和上一题(【LeetCode286】墙与门(BFS))非常相似,这题的0就相当于286题的门,但是本题是可能存在多个门“堆”在一起(多个0)的情况,首先将0加入队列,从每个0开始一圈圈向1用BFS扩散,可以设置二维数组dis记录距离,和用vis二维数组表示是否遍历过的flag。

一、题目

中等题。

image.png

提示:


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

二、思路

(1)其实和上一题(【LeetCode286】墙与门(BFS))非常相似,这题的0就相当于286题的门,但是本题是可能存在多个门“堆”在一起(多个0)的情况,首先将0加入队列,从每个0开始一圈圈向1用BFS扩散,可以设置二维数组dis记录距离,和用vis二维数组表示是否遍历过的flag。


(2)加入队列的条件是:新节点木有越界,并且还未遍历过该新节点。


ps:一开始发现只对了几个测试用例,找了好久发现是把dis[newx][newy] = dis[x][y] + 1;写成dis[newy][newy] = dis[x][y] + 1;了,,这种bug应该是要很快定位的,观察错误的样例结果分析(有几个应该是0的格子竟然有大于0的数字)。


三、代码

class Solution {
private:
    vector<pair<int, int>>directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        vector<vector<int>>vis(row, vector<int>(col));
        vector<vector<int>>dis(row, vector<int>(col));
        queue<pair<int, int>>q;
        //先将所有0的坐标入队列
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                if(matrix[i][j] == 0){
                    q.push(make_pair(i, j));
                    vis[i][j] = 1;
                }
            }
        }
        while(!q.empty()){
            pair<int, int>a = q.front();
            int x = a.first, y = a.second;
            q.pop();
            for(auto dir: directions){
                int newx = x + dir.first, newy = y + dir.second;
                if(isarea(matrix, newx, newy) && !vis[newx][newy]){
                    dis[newx][newy] = dis[x][y] + 1;
                    q.push(make_pair(newx, newy));
                    vis[newx][newy] = 1;
                }
            }
        }
        return dis;
    }
    bool isarea(vector<vector<int>>& mat, int x, int y){
        return (x >= 0 && x < mat.size() && y >= 0 && y < mat[0].size());
    }
};
相关文章
|
3月前
|
分布式计算 算法 Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本文讲解了两道经典的图论问题:**岛屿数量(LeetCode 200)** 和 **腐烂的橘子(LeetCode 994)**,分别通过 DFS/BFS 实现。在“岛屿数量”中,利用深度或广度优先搜索遍历二维网格,标记连通陆地并计数;“腐烂的橘子”则采用多源 BFS,模拟腐烂传播过程,计算最短时间。两者均需掌握访问标记技巧,是学习网格搜索算法的绝佳实践。
137 1
|
3月前
|
Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本篇博客详细解析了三道经典的动态规划问题:198. 打家劫舍(线性状态转移)、279. 完全平方数与322. 零钱兑换(完全背包问题)。通过 Go 语言实现,帮助读者掌握动态规划的核心思想及其实战技巧。从状态定义到转移方程,逐步剖析每道题的解法,并总结其异同点,助力解决更复杂的 DP 问题。适合初学者深入理解动态规划的应用场景和优化方法。
81 0
|
5月前
|
算法 Go
【LeetCode 热题100】73:矩阵置零(详细解析)(Go语言版)
这篇文章详细解析了力扣热题 73——矩阵置零问题,提供两种解法:一是使用额外标记数组,时间复杂度为 O(m * n),空间复杂度为 O(m + n);二是优化后的原地标记方法,利用矩阵的第一行和第一列记录需要置零的信息,将空间复杂度降低到 O(1)。文章通过清晰的代码示例与复杂度分析,帮助理解“原地操作”及空间优化技巧,并推荐相关练习题以巩固矩阵操作能力。适合刷题提升算法思维!
143 9
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
11月前
|
算法 C++
Leetcode第59题(螺旋矩阵2)
这篇文章介绍了解决LeetCode第59题“螺旋矩阵II”的算法,通过C++编程实现按顺时针顺序填充一个n x n的正方形矩阵。
68 0
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
144 6
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
196 4
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
170 0
【Leetcode刷题Python】73. 矩阵置零
|
存储 数据采集 算法
LeetCode题目73:矩阵置零
LeetCode题目73:矩阵置零
|
算法
力扣经典150题第三十七题:矩阵置零
力扣经典150题第三十七题:矩阵置零
82 2