【算法】BFS 系列之边权为 1 的最短路问题

【ps】本篇有 4 道 leetcode OJ。 

目录

一、算法简介

二、相关例题

1）迷宫中离入口最近的出口

.1- 题目解析

.2- 代码编写

2）最小基因变化

.1- 题目解析

.2- 代码编写

3）单词接龙

.1- 题目解析

.2- 代码编写

4）为高尔夫比赛砍树

.1- 题目解析

.2- 代码编写

---

一、算法简介

        最短路问题是图论中一种经典的题型，包括单源最短路、多源最短路、边权为 1 的最短路等等。本篇主要讲述的是边权为 1 的最短路问题。

        有如下一幅无向图，其中的每个点都可以看作是一个地点，两点之间的线可以看作是一条路径，路径上标识的权值（边权）可以看作是路径的长度，所谓最短路问题，就是求一个地点到另一个地点的最短路径长度。

         而边权为 1 的最短路问题，就是指每条路径上的权值都为 1 或都相同。

        对于这类问题，通常是借助 BFS，结合哈希表来得出一个最优解，其中，BFS 通过模拟一个队列的入队和出队来完成，而哈希表用来标识某一个地点是否已经遍历过。

        之所以能用 BFS 得到最优解，是因为在入队和出队的过程中，一定会有一次层序遍历比另一次先到达某个地点。例如下图中，A到达E有两条路径，但由于边权为 1，A->C->E 一定比 A->B->D->E 更短，且由于 BFS 是层序遍历的，从 A 点同时出发，一层一层向外扩展的，因此 E 点一定和 D 点同时入队，此时 A->C->E 已经走完了，A->B->D->E 才走到 D 还没走到 E，因此在进行 BFS 时，是能够区分最短路径，能够找到最优解的。

        而最短路径其实就是，从起点到终点进行 BFS 时所扩展的层数。

 

二、相关例题

1）迷宫中离入口最近的出口

1926. 迷宫中离入口最近的出口

 

.1- 题目解析

        如果把小人最初所在的位置当作是一个地点，两个格子之间是一条长度为 1 的路径，那么这道题就可以抽象成是边权为 1 的最短路问题。

        我们直接使用 BFS 遍历路径和地点即可。 

.2- 代码编写

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>& e) {int m=maze.size(),n=maze[0].size();bool vis[m][n];    //记录地点是否被遍历过memset(vis,0,sizeof(vis));queue<pair<int,int>> q;//通过队列的入队和出队来实现BFSq.push({e[0],e[1]});vis[e[0]][e[1]]=true;int step=0; //记录扩展的层数while(q.size()){step++;//每次向外扩展一层都要记录int sz=q.size();//每次取队长，方便出队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>=0 && x<m && y>=0 && y<n && maze[x][y]=='.' && !vis[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;}
};

2）最小基因变化

433. 最小基因变化

 

.1- 题目解析

        字符串 AAAA 可以变化成 CAAA、GAAA、TAAA 等等，如果将这些字符串看作是一个地点，那么由一个字符串变化成另一个字符串的过程，就可以抽象成是边权为 1 的最短路问题。

.2- 代码编写

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 change="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.size()){ret++;int sz=q.size();while(sz--){string t=q.front();q.pop();//暴力枚举所有可变的字符组合for(int i=0;i<8;i++)//遍历原字符组合{string tmp=t;//细节问题for(int j=0;j<4;j++)//遍历可变化的字符{tmp[i]=change[j];if(hash.count(tmp)&&!vis.count(tmp))//当前枚举的一种字符组合在基因库中存在{if(tmp==endGene) //若已枚举出最终结果，则直接返回return ret;q.push(tmp);    //否则继续BFS枚举字符组合vis.insert(tmp);}}}}}return -1;}
};

3）单词接龙

127. 单词接龙

 

.1- 题目解析

        本题与上一道题几乎一模一样，也可以将符串看作是一个地点，将一个字符串变化成另一个字符串的过程抽象成是边权为 1 的最短路问题。

.2- 代码编写

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> hash(wordList.begin(),wordList.end());unordered_set<string> vis;if(!hash.count(endWord))return 0;queue<string> q;q.push(beginWord);vis.insert(beginWord);int ret=1;//统计一共有多少个单词while(q.size()){ret++;int sz=q.size();while(sz--){string t=q.front();q.pop();//暴力枚举所有可变化的字符组合for(int i=0;i<t.size();i++){string tmp=t;for(char ch='a';ch<='z';ch++){tmp[i]=ch;if(hash.count(tmp) && !vis.count(tmp)){if(tmp==endWord)return ret;q.push(tmp);vis.insert(tmp);}}}}}return 0;}
};

4）为高尔夫比赛砍树

675. 为高尔夫比赛砍树

 

.1- 题目解析

        先找出砍树的顺序，然后按照砍树的顺序，一个一个用 BFS 求出最短路即可。

.2- 代码编写

class Solution {int m,n;
public:int cutOffTree(vector<vector<int>>& forest) {m=forest.size(),n=forest[0].size();//找砍树的顺序vector<pair<int,int>> 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 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]:trees){int step=bfs(forest,bx,by,a,b);//找起始位置到终止位置的最短路径if(step==-1)return -1;ret+=step;bx=a,by=b;//继续遍历下一个位置}return ret;}bool vis[51][51];int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};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;memset(vis,0,sizeof(vis));//每次重新标识bfsq.push({bx,by});vis[bx][by]=true;int step=0;while(q.size()){step++;int sz=q.size();while(sz--){auto [a,b]=q.front();q.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] && !vis[x][y]){if(x==ex && y==ey)return step;q.push({x,y});vis[x][y]=true;}}}}return -1;}};