【优选算法】BFS解决边权为1的最短路径问题 {单源最短路径；多源最短路径}

一、经验总结

最短路径算法是一种用于找到图或网络中两个节点之间最短路径的算法。它被广泛应用于网络路由、GPS导航、交通规划和其他领域。

单源最短路径

在这里插入图片描述

用BFS解决边权为1的单源最短路径问题：

  1. 利用队列辅助完成BFS
  2. 定义visited数组或是哈希表标记已访问，防止重复入队列访问
  3. 创建横纵坐标的变化量数组，可以方便地遍历相邻地四个方向
  4. 定义变量k统计每层节点的数量，控制一层一层的遍历，遍历到终点立即返回。BFS扩展的层数就是最短路径的长度。

多源最短路径

在这里插入图片描述

用BFS解决边权为1的多源最短路径问题：

  1. 多源：多个源点，一个终点
  2. 从所有的源点出发进行BFS，其他步骤同单源最短路径相同

二、相关编程题

2.1 单源最短路径

2.1.1 迷宫中离入口最近的出口

题目链接

1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

就是求入口到出口的最短路径（单元最短路径），算法原理上面已经讨论过。

编写代码

class Solution {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        bool visited[m][n];
        memset(visited, 0, sizeof(visited));
        queue<pair<int,int>> que;
        que.push({entrance[0], entrance[1]});
        visited[entrance[0]][entrance[1]] = true;
        int ret = 0;
        while(!que.empty())
        {
            ++ret; //扩展的层数就是最短路径的长度   
            int k = que.size(); //要控制一层一层地向外拓展
            while(k--)
            {
                auto [a,b] = que.front();
                que.pop();
                for(int i = 0; i < 4; ++i)
                {
                    int x = a+dx[i], y = b+dy[i];
                    if(x>=0 && x<m && y>=0 && y<n && maze[x][y]=='.' && !visited[x][y])
                    {
                        if(x==0 || y==0 || x==m-1 || y==n-1) return ret; //遇到出口直接返回
                        que.push({x,y});
                        visited[x][y] = true;
                    }
                }
            }
        }
        return -1; //找不到出口返回-1
    }
};

2.1.2 最小基因变化

题目链接

433. 最小基因变化 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> hashBank(bank.begin(), bank.end()), visited;
        if(!hashBank.count(endGene)) return -1;
        if(startGene == endGene) return 0;
        string change = "ACGT";
        queue<string> que;
        que.push(startGene);
        visited.insert(startGene);
        int cnt = 0;
        while(!que.empty())
        {
            ++cnt;
            int k = que.size();
            while(k--)
            {
                string gene = que.front();
                que.pop();
                for(int i = 0; i < gene.size(); ++i)
                {
                    string tmp = gene; //注意要创建临时数组，不能修改原数组
                    for(int j = 0; j < 4; ++j) 
                    {
                        tmp[i] = change[j];
                        if(hashBank.count(tmp) && !visited.count(tmp))
                        {
                            if(tmp == endGene) return cnt;
                            que.push(tmp);
                            visited.insert(tmp);
                        }
                    }
                }
            }
        }
        return -1;
    }
};

2.1.3 单词接龙

题目链接

127. 单词接龙 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

同上

编写代码

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        unordered_set<string> visited;
        if(beginWord == endWord) return 1;
        if(!dict.count(endWord)) return 0;
        queue<string> que;
        que.push(beginWord);
        visited.insert(beginWord);
        int ret = 1;
        while(!que.empty())
        {
            ++ret;
            int k = que.size();
            while(k--)
            {
                string word = que.front();
                que.pop();
                for(int i = 0; i < word.size(); ++i)
                {
                    string tmp = word;
                    for(char j = 'a'; j <= 'z'; ++j)
                    {
                        tmp[i] = j;
                        if(dict.count(tmp) && !visited.count(tmp))
                        {
                            if(tmp == endWord) return ret;
                            que.push(tmp);
                            visited.insert(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};

2.1.4 为高尔夫比赛砍树

题目链接

675. 为高尔夫比赛砍树 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

按照树的高度从低到高的顺序砍掉所有的树，计算砍完所有树需要走的最短路径。实际上就是使用多次BFS，按顺序计算一棵树到下一棵树的最短路径，最后将所有途径的最短路径加起来就是最终结果。

编写代码

class Solution {
    typedef pair<int,int> PII;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int m, n;
public:
    int cutOffTree(vector<vector<int>>& forest) {
        m = forest.size(), n = forest[0].size();
        //汇总所有树的坐标
        vector<PII> trees;
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(forest[i][j] > 1) trees.push_back({i,j});
		//按高度升序排序
        sort(trees.begin(), trees.end(), [&](const PII &p1, const PII &p2)
        {
            return forest[p1.first][p1.second] < forest[p2.first][p2.second];
        });
   		//按照树的高度从低到高砍树
        int ret = 0;
        PII startp = {0,0};
        for(int i = 0; i < trees.size(); ++i)
        {
            int step = BFS(forest, startp, trees[i]); //计算所站位置到要砍的树的最短距离
            if(step == -1) return -1; //如果无法砍完所有的树，返回-1
            ret+=step; //将所有的最短距离加起来
            startp = trees[i]; //从砍树位置继续找下一棵树
        }
        return ret;
    }

    int BFS(vector<vector<int>>& forest, const PII& startp, const PII& endp)
    {
        auto [sx, sy] = startp;
        auto [ex, ey] = endp;
        if(sx == ex && sy == ey) return 0;
        int visited[m][n];
        memset(visited, 0, sizeof(visited));
        queue<PII> que;
        que.push(startp);
        visited[sx][sy] = true;
        int step = 0;
        while(!que.empty())
        {
            ++step;
            int k = que.size();
            while(k--)
            {
                auto [a, b] = que.front();
                que.pop();
                for(int i = 0; i < 4; ++i)
                {
                    int x = a+dx[i], y = b+dy[i];
                    if(x>=0 && x<m && y>=0 && y<n && forest[x][y] && !visited[x][y])
                    {
                        if(x == ex && y == ey) return step;
                        que.push({x, y});
                        visited[x][y] = true;
                    }
                }
            }
            
        }
        return -1;
    }
};

2.2 多源最短路径

2.2.1 矩阵

题目链接

542. 01 矩阵 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

class Solution {
    typedef pair<int, int> PII;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        //ret[x][y] == -1 表示没有访问过（取代visited数组）
        //ret[x][y] > -1 表示到最近0的距离（不需要step记录每层节点的数量）
        vector<vector<int>> ret(m, vector<int>(n, -1));
        queue<PII> que;
        //将所有的源点加入到队列
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(mat[i][j] == 0)
                {
                    ret[i][j] = 0;
                    que.push({i,j});
                }
            }
        }
        //多源BFS
        while(!que.empty())
        {
            auto [a, b] = que.front();
            que.pop();
            for(int i = 0; i < 4; ++i)
            {
                int x = a+dx[i], y = b+dy[i];
                if(x>=0 && x<m && y>=0 && y<n && ret[x][y] == -1)
                {
                    ret[x][y] = ret[a][b]+1;
                    que.push({x,y});
                }
            }
        }
        return ret;
    }
};

2.2.2 飞地的数量

题目链接

1020. 飞地的数量 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

class Solution {
    typedef pair<int, int> PII;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> t_grid(m, vector<int>(n)); //拷贝原矩阵
        queue<PII> que;
        //将所有边界上的1都加入队列，并将矩阵修改为0（已访问）
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
            {    
                t_grid[i][j] = grid[i][j];
                if((i==0 || j==0 || i==m-1 || j==n-1) && grid[i][j]==1)
                {
                    que.push({i, j});
                    t_grid[i][j] = 0;
                }        
            }
		//以所有边界上的1为起点进行多源BFS，将所有边界上的连接块修改为0
        while(!que.empty())
        {
            auto [a, b] = que.front();
            que.pop();
            for(int i = 0; i < 4; ++i)
            {
                int x = a+dx[i], y = b+dy[i];
                if(x>=0 && x<m && y>=0 && y<n && t_grid[x][y]==1)
                {
                    t_grid[x][y] = 0;
                    que.push({x,y});
                }
            }
        }
        //统计矩阵中剩余的值为1的陆地
        int ret = 0;
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(t_grid[i][j] == 1) ++ret;
        return ret;
    }
};

2.2.3 地图中的最高点

题目链接

1765. 地图中的最高点 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

同2.2.1矩阵

编写代码

class Solution {
    typedef pair<int, int> PII;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size(), n = isWater[0].size();
        vector<vector<int>> ret(m, vector<int>(n, -1));
        queue<PII> que;
        for(int i=0; i<m; ++i)
            for(int j=0; j<n; ++j)
            {
                if(isWater[i][j] == 1)
                {
                    que.push({i,j});
                    ret[i][j] = 0;
                }
            }
        while(!que.empty())
        {
            auto [a,b] = que.front();
            que.pop();
            for(int i = 0; i < 4; ++i)
            {
                int x = a+dx[i], y = b+dy[i];
                if(x>=0 && x<m && y>=0 && y<n && ret[x][y]==-1)
                {
                    ret[x][y] = ret[a][b]+1;
                    que.push({x,y});
                }
            }
        }
        return ret;
    }
};

2.2.4 地图分析

题目链接

1162. 地图分析 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

同2.2.1矩阵，只不过这道题不是要求所有海洋到陆地的最短距离（返回矩阵），而是海洋到陆地最短距离的最大值（单个值）。

因此我们仍然采用多源BFS+visited矩阵+step计层的方案，多源BFS拓展的层数就是海洋到陆地的最短距离，遍历到最后就是最短距离的最大值

当然也可以使用多源BFS+dist矩阵的方案

编写代码

class Solution {
    typedef pair<int, int> PII;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    int maxDistance(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        queue<PII> que;
		//将所有陆地加入到队列（作为起点）
        for(int i=0; i<m; ++i)
            for(int j=0; j<n; ++j)
            {
                if(grid[i][j] == 1)
                {
                    que.push({i,j});
                    visited[i][j] = true;
                }
            }
        //多源BFS
        int step = -1; //step计层
        while(!que.empty())
        {
            ++step;
            int k = que.size();
            while(k--)
            {
                auto [a,b] = que.front();
                que.pop();
                for(int i = 0; i < 4; ++i)
                {
                    int x = a+dx[i], y = b+dy[i];
                    if(x>=0 && x<m && y>=0 && y<n && !visited[x][y])
                    {
                        que.push({x,y});
                        visited[x][y] = true;
                    }
                }
            }
        }
        return step == 0? -1:step; //全是陆地或海洋返回-1
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/683505.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

用 Axios 封装一个双 token 无感刷新

用 Axios 封装一个双 token 无感刷新

为什么要用双Token无感刷新&#xff0c;它解决了什么问题&#xff1f; 为了保证安全性&#xff0c;后端设置的Token不可能长期有效&#xff0c;过了一段时间Token就会失效。而发送网络请求的过程又是需要携带Token的&#xff0c;一旦Token失效&#xff0c;用户就要重新登陆&…
阅读更多...
JMH307【亲测】 怀旧端游【WD】1.73单机版带GM后台视频安装教程虚拟机端

JMH307【亲测】 怀旧端游【WD】1.73单机版带GM后台视频安装教程虚拟机端

资源介绍&#xff1a; 是否需要虚拟机&#xff1a;是 文件大小&#xff1a;压缩包约8G 支持系统&#xff1a;win7、win10、win11 硬件需求&#xff1a;运行内8G 4核及以上CPU 资源截图&#xff1a; 下载地址
阅读更多...
微软不再允许Windows 11通过1@1.com绕过登录 但还有其他办法可以继续用

微软不再允许Windows 11通过1@1.com绕过登录 但还有其他办法可以继续用

微软不再允许 Windows 11 通过 11.com 和 nothankyou.com 绕过登录&#xff0c;但断网的情况下使用 OOBE\BYPASSNRO 命令仍然是有效的。如果你在安装或重置系统时仍然需要创建本地账户&#xff0c;请直接使用 OOBE 命令。 在 Windows 11 家庭版和专业版中用户必须保持设备联网…
阅读更多...
基于小波域优化Savitzky–Golay滤波器的脑电图信号的运动伪影去除方法（MATLAB R2018A）

基于小波域优化Savitzky–Golay滤波器的脑电图信号的运动伪影去除方法（MATLAB R2018A）

在获取或采集数据的过程中&#xff0c;不可避免地将噪声引入到数据中&#xff0c;噪声的存在使得原始数据发生变异&#xff0c;对数据的处理及分析产生严重地影响。常用的去噪模型有平滑去噪、均值去噪。其中&#xff0c;平滑去噪又包括移动平均平滑法和Savitzky-Golay卷积平滑…
阅读更多...
如何在npm上发布自己的包

如何在npm上发布自己的包

如何在npm上发布自己的包 npm创建自己的包 一、一个简单的创建 1、创建npm账号 官网&#xff1a;https://www.npmjs.com/创建账号入口&#xff1a;https://www.npmjs.com/signup 注意&#xff1a;需要进入邮箱验证 2、创建目录及初始化 $ mkdir ufrontend-test $ cd ufron…
阅读更多...
演讲全文｜林涛：MongoDB助力智能制造出海控本增效

演讲全文｜林涛：MongoDB助力智能制造出海控本增效

5月29日-30日在上海世博中心举办的亚马逊云科技中国峰会圆满结束。本文整理了MongoDB北亚区方案与咨询总监林涛在白金讲堂的演讲全文&#xff0c;就《MongoDB助力智能制造出海控本增效》话题与大家共同探讨。 白金讲堂演讲视频 从全球经济竞争的角度看&#xff0c;中国制造业…
阅读更多...
【Python】认识 Python

【Python】认识 Python

一、计算机基础概念 1、什么是计算机 很多老一辈的人&#xff0c;管下面这个叫做计算机。然而&#xff0c;它只是 “计算器”&#xff0c;和计算机是有很大区别的。 现在我们所说的计算机&#xff0c;不光能进行算术运算&#xff0c;还能进行逻辑判断、数据存储、网络通信等…
阅读更多...
【Vue】路由介绍

【Vue】路由介绍

一、引入 思考 单页面应用程序&#xff0c;之所以开发效率高&#xff0c;性能好&#xff0c;用户体验好 最大的原因就是&#xff1a;页面按需更新 比如当点击【发现音乐】和【关注】时&#xff0c;只是更新下面部分内容&#xff0c;对于头部是不更新的 要按需更新&#xff…
阅读更多...
Nginx 功能简介及代理配置

Nginx 功能简介及代理配置

一、Nginx功能简介 Nginx是一款开源的高性能HTTP和反向代理服务器&#xff0c;具有轻量级的设计、高并发能力、内存占用低以及配置简单等特点&#xff0c;并且支持热部署。以下是Nginx的主要功能&#xff1a; 静态内容服务&#xff1a;Nginx可以作为一个高性能的静态文件服务…
阅读更多...
QML应用添加网络代理

QML应用添加网络代理

在QML应用中我们可以通过QNetworkProxy和QNetworkAccessManager类给应用添加网络代理。QNetworkProxy是Qt网络模块中的一个类，用于配置网络请求的代理服务器。通过使用代理服务器，我们可以控制应用程序的网络流量，实现网络请求的转发、监视、和过滤等功能。代理服务器在很多…
阅读更多...
【Python】 Python应用的最佳项目结构解析

【Python】 Python应用的最佳项目结构解析

基本原理 在Python开发中&#xff0c;一个清晰且结构化良好的项目布局对于项目的可维护性、可扩展性和团队协作至关重要。项目结构不仅影响代码的组织方式&#xff0c;还影响到开发流程和部署策略。一个优秀的项目结构应该能够方便地进行模块化开发&#xff0c;易于理解&#…
阅读更多...
keil下载及安装(社区版本)

keil下载及安装(社区版本)

知不足而奋进 望远山而前行 目录 文章目录 前言 Keil有官方版本和社区版本&#xff0c;此文章为社区版本安装&#xff0c;仅供参考。 1.keil MDK 2.keil社区版介绍 3.keil下载 (1)打开进入登录界面 (2)点击下载,跳转到信息页面 (3)填写个人信息,点击提交 (4)点击下载…
阅读更多...
巨详细Linux卸载Redis教程

巨详细Linux卸载Redis教程

巨详细Linux卸载Redis教程 1、检查系统残留redis数据2、卸载系统残留redis数据 1、检查系统残留redis数据 redis等数据相关中间件安装前一定要进行残留数据检查&#xff0c;排除后期存在的各种隐患。 #检查有没有残留客户端 whereis redis-cli #检查有没有残留服务 whereis r…
阅读更多...
上位机图像处理和嵌入式模块部署（f407 mcu中的spi总线操作）

上位机图像处理和嵌入式模块部署（f407 mcu中的spi总线操作）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 前面我们学习mcu&#xff0c;一般都是模板和模块之间的接口&#xff0c;比如说串口、usb、eth这种。还有一种接口&#xff0c;更多的是芯片和芯片之…
阅读更多...
【Python】 深入理解Pandas中的iloc和loc：数据选择的艺术

【Python】 深入理解Pandas中的iloc和loc：数据选择的艺术

基本原理 在Python的Pandas库中&#xff0c;数据选择是数据分析和处理的基础。iloc和loc是两种常用的数据选择方法&#xff0c;它们都允许用户根据索引位置或标签来选择数据。然而&#xff0c;它们在行为和用途上存在一些关键的差异。 iloc iloc是基于整数索引的&#xff0c…
阅读更多...
【Modelground】个人AI产品MVP迭代平台（3）——工程化架构设计

【Modelground】个人AI产品MVP迭代平台（3）——工程化架构设计

文章目录 背景monorepo多项目调试/打包公共静态资源服务公共模型拷贝入项目的public文件夹总结 背景 Modelground中的项目&#xff0c;基本都依赖Mediapipe模型&#xff0c;因此&#xff0c;有很强的需要对Mediapipe进行封装&#xff0c;其余项目都调用这个封装库。从架构上&a…
阅读更多...
IIS漏洞

IIS漏洞

IIS7.5解析漏洞 安装IIS7.5 安装完成之后直接访问浏览器&#xff1a; 安装phpstudy for IIS 安装这个的目的是方便&#xff0c;不用自己去配置 解压开傻瓜式安装即可。然后查看探针&#xff1a; 漏洞原理 IIS7/7.5在Fast-CGI运行模式下,在一个文件路径(/shell.jpg)后面加上/…
阅读更多...
linux线程的同步与互斥

linux线程的同步与互斥

前面我们讲了线程的概念以及如何创建与控制线程&#xff0c;接下来我们来对线程的细节与线程之间的问题进行一些讲解&#xff1b; 1.线程的互斥 互斥就是相互排斥&#xff0c;我们可以理解为对立竞争不相容&#xff1b;线程的互斥则是线程之间在对于临界资源竞争时相互排斥的…
阅读更多...
openh264 编码命令行工具源码分析

openh264 编码命令行工具源码分析

openh264 OpenH264 是由 Cisco 公司发布的一个开源的 H.264 编码和解码器。它提供了命令行工具&#xff0c;可以用于对视频进行编码和解码操作。 使用说明 openh264 编码命令行工具可以使用命令行或 config 配置进行编码操作。编译和使用方法具体可以参考 Windows11编译open…
阅读更多...
12_JavaWebAjax

12_JavaWebAjax

文章目录 Ajax1. 同步请求异步请求2. Ajax实现方式3. 日程管理第四期4. 响应JSON串4.1 响应JSON串格式的一般格式 Appendix Ajax 发送请求的一些方式 1.输入浏览器回车 2.html>head>script/link ​ img标签 3.a标签form表单标签等 用户手动控制提交产生&#xff1b…
阅读更多...
最新文章

Copyright @ 2022~2023