BFS解决单源最短路问题

2024-08-20 19:12
文章标签 问题 bfs 解决 单源 短路

本文主要是介绍BFS解决单源最短路问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

迷宫中离入口最近的出口

最小基因变化

单词接龙

为高尔夫比赛砍树


迷宫中离入口最近的出口

题目

思路

使用宽度优先遍历解决这道题,需要一个二维数组标记是否被遍历过,也需要一个队列辅助完成宽度优先遍历,类似于水波纹一样,一层一层的往外扩,如果扩到了矩阵边缘行,则返回步数,就是离入口最近的距离。

代码

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();vector<vector<bool>> vis(m,vector<bool>(n,false));queue<pair<int,int>> q;int step=0;q.push({entrance[0],entrance[1]});vis[entrance[0]][entrance[1]]=true;while(!q.empty()){int sz=q.size();step++;for(int i=0;i<sz;i++){int a=q.front().first;int b=q.front().second;q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0 && x<m && y>=0 &&y<n && !vis[x][y] && maze[x][y]=='.'){if(x==0 || x==m-1 || y==0 || y==n-1)return step;q.push({x,y});vis[x][y]=true;}}}}return -1;}
};
最小基因变化

题目

思路

其实仔细分析这道题后可以发现,也可以用宽度优先遍历来解决这道题,每一次某位置变化一个字母,就相当于以某位置为起点往外扩了一层,为了便于快速地判断变换后的基因序列是否在基因库中,将基因库中的基因序列存储到哈希表中,同时也需要一个哈希表来标记某些基因序列是否已经变换过,另外也需要一个队列来完成宽度优先遍历的辅助操作。

需要注意的是,在对基因序列的某位置变换前,需保存一下变换前的基因序列,便于变换后再进行恢复还原。

代码

class Solution {
public:int minMutation(string startGene, string endGene, vector<string>& bank) {unordered_set<string> vis;unordered_set<string> hash(bank.begin(),bank.end());string s="ACGT";if(startGene==endGene) return 0;if(!hash.count(endGene)) return -1;queue<string> q;q.push(startGene);vis.insert(startGene);int ret=0;while(!q.empty()){int sz=q.size();ret++;for(int k=0;k<sz;k++){string top=q.front();q.pop();for(int i=0;i<8;i++){string str=top;for(int j=0;j<4;j++){top[i]=s[j];if(top==endGene) return ret;if(!vis.count(top) && hash.count(top))q.push(top),vis.insert(top);}top=str;}}}return -1;}
};
单词接龙

题目

思路

其实这道题和前一道题是类似的,只不过这道题的单词变化范围不再是'A','C','G','T',而是26个英文小写字母,为了快速判断单词是否是字典中的单词,首先将字典中的单词存放到哈希表中,同时也需要一个哈希表标记已经访问过的单词和一个队列来完成宽度优先遍历的辅助操作。

这道题同上一道题一样,进行单词的某位置前需要先保存原始单词,以便变换完单词某位置后进行恢复和还原。

代码

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> vis;unordered_set<string> hash(wordList.begin(),wordList.end());if(!hash.count(endWord)) return 0;queue<string> q;q.push(beginWord);vis.insert(beginWord);int ret=1;while(!q.empty()){int sz=q.size();ret++;for(int i=0;i<sz;i++){string top=q.front();q.pop();for(int j=0;j<beginWord.size();j++){string str=top;for(char ch='a';ch<='z';ch++){top[j]=ch;if(top==endWord) return ret;if(!vis.count(top) && hash.count(top))q.push(top),vis.insert(top);}top=str;}}}return 0;}
};
为高尔夫比赛砍树

题目

思路

解决这道题也是使用宽度优先遍历来解决,但是题目要求按高度从低到高砍完所有的树,因此需要对砍树的顺序进行排序,然后求出被砍顺序挨着的两个树的最短距离,分别求出这样的被砍顺序挨着的两个树的最短距离,然后加起来,就是按高度从低到高砍完所有树的最短步数,如果某一步不能正常进行,说明无法完成砍树,直接返回-1.

代码

class Solution {int m,n;int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};public:int cutOffTree(vector<vector<int>>& forest) {m=forest.size(),n=forest[0].size();vector<pair<int,int>> order;for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(forest[i][j]>1)order.push_back({i,j});sort(order.begin(),order.end(),[&](const pair<int,int>& p1,const pair<int,int>& p2){return forest[p1.first][p1.second]<forest[p2.first][p2.second];});int bx=0,by=0;int ret=0;for(auto& [a,b]:order){int step=bfs(forest,bx,by,a,b);if(step==-1) return -1;ret+=step;bx=a,by=b;}return ret;}int bfs(vector<vector<int>>& forest,int bx,int by,int ex,int ey){if(bx==ex && by==ey) return 0;queue<pair<int,int>> q;bool vis[51][51];memset(vis,false,sizeof vis);q.push({bx,by});vis[bx][by]=true;int step=0;while(!q.empty()){int sz=q.size();step++;for(int i=0;i<sz;i++){auto [a,b]=q.front();q.pop();for(int j=0;j<4;j++){int x=a+dx[j],y=b+dy[j];if(x==ex && y==ey) return step;if(x>=0 && x<m && y>=0 && y<n && forest[x][y] && !vis[x][y])q.push({x,y}),vis[x][y]=true;}}}return -1;}
};

这篇关于BFS解决单源最短路问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1090934

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

如何解决线上平台抽佣高 线下门店客流少的痛点!

目前,许多传统零售店铺正遭遇客源下降的难题。尽管广告推广能带来一定的客流,但其费用昂贵。鉴于此,众多零售商纷纷选择加入像美团、饿了么和抖音这样的大型在线平台,但这些平台的高佣金率导致了利润的大幅缩水。在这样的市场环境下,商家之间的合作网络逐渐成为一种有效的解决方案,通过资源和客户基础的共享,实现共同的利益增长。 以最近在上海兴起的一个跨行业合作平台为例,该平台融合了环保消费积分系统,在短

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k