【LeetCode286】墙与门(BFS)

简介: -1 表示墙或是障碍物0 表示一扇门

一、题目

给定一个 m × n 的二维网格,网格中有以下三种可能的初始化值:


-1 表示墙或是障碍物

0 表示一扇门

INF 无限表示一个空的房间。然后,我们用 2 31 2^{31}2

31

 - 1 = 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。


你要给每个空房间位上填上该房间到 最近门的距离,如果无法到达门,则填 INF 即可。

image.png

样例1:

输入:
[[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
输出:
[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
解释:
2D网络为:
INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF
答案为:
  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

二、思路

(1)先将所有门入队,从所有门开始BFS,入队的是点坐标,可以用pair结构。

(2)入队时更新距离,而不是出队时,防止重复入队。

(3)更新的条件是rooms[newx][newy] > rooms[x][y] + 1,这里的rooms[x][y] + 1在本轮次(从该当前门开始BFS)遍历中本该属于该节点的树高度,如果这个高度(路径)更小自然就要更新了。


三、代码

class Solution {
private:
    vector<pair<int, int>>directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if(rooms.empty()){
            return;
        }
        int row = rooms.size();
        int col = rooms[0].size();       
        queue<pair<int, int>> q;
        //先将所有门入队
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(rooms[i][j] == 0){
                    q.push(make_pair(i, j));
                }
            }
        }
        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(rooms, newx, newy) && rooms[newx][newy] > rooms[x][y] + 1){
                    q.push(make_pair(newx, newy));
                    rooms[newx][newy] = rooms[x][y] + 1;
                }
            }
        }
    }
    bool isarea(vector<vector<int>>&rooms, int x, int y){
        return (x >= 0 && x < rooms.size() && y >= 0 && y < rooms[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
【Leetcode 2583】二叉树中的第K大层和 —— 优先队列 + BFS
解题思路: - 使用队列保存节点,按层序依次保存该层节点 - 使用优先队列保存每层节点值的总和,最后剔除前k个大数即可得到
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
存储 算法 数据可视化
广度优先搜索(BFS)+回溯解决LeetCode 126题:单词接龙 II
广度优先搜索(BFS)+回溯解决LeetCode 126题:单词接龙 II
|
存储 算法 数据可视化
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
|
搜索推荐 Java
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
|
算法
leetcode-675:为高尔夫比赛砍树 (最短路径算法bfs,dijkstra,A*)
leetcode-675:为高尔夫比赛砍树 (最短路径算法bfs,dijkstra,A*)
121 0
|
算法 安全 Android开发
LeetCode 周赛上分之旅 # 37 多源 BFS 与连通性问题
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
148 0
|
边缘计算 缓存 算法
LeetCode 双周赛 102,模拟 / BFS / Dijkstra / Floyd
昨晚是 LeetCode 双周赛第 102 场,你参加了吗?这场比赛比较简单,拼的是板子手速,继上周掉大分后算是回了一口血 😁。
207 0