产品开发计划书_网易企业邮箱服务器怎么设置_百度竞价广告的位置_外链工具xg

引言

上篇我们介绍了BFS算法求取最短路径的代码实现，本篇将结合具体题目，进一步深化对于该方法的理解运用。

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

1.1 题目链接：https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/

1.2 题目分析：

• 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）。
• 同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
• 可以上下左右在空格子内进行移动，无法穿过墙，要求寻找距离入口最近的出口
• 每移动一次视为移动一步，求出最短步数

1.3 思路讲解：

利用层序遍历的思想，一层则可视为一步，其余步骤与上题基本相同。
注意处理边界情况！！！

1.4 代码实现:

class Solution {
public:int dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};int step=0;bool vis[101][101]={false};//标记数组int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int m=maze.size(),n=maze[0].size();queue<pair<int,int>> q;q.push({entrance[0],entrance[1]});//起点入队列vis[entrance[0]][entrance[1]]=true;while(q.size()){step++;int sz=q.size();for(int i=0;i<sz;i++){auto [a,b]=q.front();q.pop();vis[a][b]=true;//下一层入队列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]==false){//判断是否为出口if(x==0 || x==m-1 || y==0 || y==n-1){return step;}q.push({x,y});vis[x][y]=true;}}}}return -1;}
};

二. 最小基因变化

2.1 题目链接：https://leetcode.cn/problems/minimum-genetic-mutation/description/

2.2 题目分析：

• 一个基因序列由8个字符构成，字符只能为A，C，G，T
• 给出start和end序列，以及基因库bank，每次可以对start内的一个字符进行A，C，G，T的变化
• 每次变化后的序列都要在bank中，求取最少变化次数
• 若无法变化成功，则返回-1

2.3 思路讲解：

首先考虑特殊情况：

• 如果start==end，说明无须变化，直接返回次数0
• 如果end不在bank内，说明不可能变化成功，直接返回-1

由于每次变化只能在ACGT的范围内，因此我们可以先定义一个string change=ACGT，类比之前变化时的数组dx和dy

• 根据之前讲解的BFS思想，我们考虑创建一个标记数组vis，以及hash来判断变化后的字符串temp是否处于bank内。
• 之后创建一个队列，将start序列入队列，根据层序遍历，每次对其进行ACGT的变化，因此一层就相当于变化一次，记录变化次数ret
• 如果变化后的序列与end相等且在bank内，则说明变化成功，直接返回ret
• 如果不相等且temp处于bank内，则将变化后的序列及录入vis内，避免重复判断

2.4 代码实现：

class Solution {
public:int minMutation(string startGene, string endGene, vector<string>& bank) {unordered_set<string> vis;//标记数组unordered_set<string> hash(bank.begin(),bank.end());//处理特殊情况if(startGene==endGene) return 0;if(!hash.count(endGene)) return -1;string change="ACGT";//每次的变化序列queue<string> q;q.push(startGene);vis.insert(startGene);int ret=0;//变化次数while(q.size()){ret++;//每层次数加1int sz=q.size();while(sz--){string t=q.front();q.pop();for(int i=0;i<8;i++){string temp=t;//避免污染源字符串for(int j=0;j<4;j++){temp[i]=change[j];if(temp==endGene && hash.count(endGene)){return ret;}//成功情况if(temp!=endGene && hash.count(temp) && !vis.count(temp)){vis.insert(temp);q.push(temp);}}}}}return -1;}
};

三. 单词接龙

3.1 题目链接：https://leetcode.cn/problems/word-ladder/description/

3.2 题目分析：

本题与上题基因变化类似，都是给出start与end，每次变化一个字母，求最小变化次数

• 每次变化一个字母后，字符串temp必须在给定的数组wordlist内
• 如果无法成功变化为end，则返回0

3.3 思路讲解：

首先考虑特殊情况：

• 如果end不在wordlist内，无论如何也无法成功变化，因此直接返回0

剩余思路与上题完全一致，只需要将遍历方向改为26个字符a->z即可。

注意本题要返回的是长度，start也算一个字符串，因此要在最小变化次数的基础上再加1

3.4 代码实现：

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;}int ret=1;//返回长度queue<string> q;q.push(beginWord);vis.insert(beginWord);while(q.size()){ret++;//每层长度+1int sz=q.size();while(sz--){string t=q.front();q.pop();int m=t.size();//该单词长度for(int i=0;i<m;i++){for(char ch='a';ch<='z';ch++){string temp=t;//避免污染源字符串temp[i]=ch;if(temp==endWord){return ret;}//成功情况if(temp!=endWord && hash.count(temp) && !vis.count(temp)){vis.insert(temp);q.push(temp);}}}}}return 0;}
};

四. 为高尔夫比赛砍树

4.1 题目链接：https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/

4.2 题目分析：

给定一个m*n的矩阵，其中

• 0表示障碍，无法行走
• 1表示地面，可以通行
• 大于1的数表示该处存在一棵树，且值的大小为树的高度，可以通行

要求从(0,0)开始，按照树的高度从低到高砍完所有树,且每次砍树之后，该处变为1

返回砍完所有树所需的最小步数

如果无法砍完所有树，则返回-1

4.3 思路讲解：

首先我们需要明确，只有遇到0时，才无法通行

• m*n的矩阵可以类比之前的迷宫问题，定义dx和dy数组，进行方向上的移动
• 遍历矩阵，按照树的高度由低到高用数组trees存储树节点

由于题目要求从低到高进行砍树，因此本题就转化为遍历trees，求两两相邻节点的最小步数之和。

求取两个点的最短路径，bfs遍历即可。

4.4 代码实现：

class Solution {
public:int dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};int m,n;//数组规模int ret=0;//最终步数bool vis[51][51];//标记数组int bfs(vector<vector<int>>& forest,int bx,int by,int ex,int ey){queue<pair<int,int>> q;int step=0;//步数memset(vis,0,sizeof(vis));//重置清零操作//处理特殊情况if(bx==ex && by==ey){return 0;}q.push({bx,by});//起点入队列vis[bx][by]=true;//更新标记while(q.size()){int sz=q.size();step++;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 && vis[x][y] == false &&forest[x][y]){if (x == ex && y == ey){return step;}//成功情况q.push({x,y});vis[x][y]=true;}}}}return -1;//未成功找到}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>& a,const pair<int,int>& b){return forest[a.first][a.second]<forest[b.first][b.second];});int bx=0,by=0;//起点for(auto& [a,b] :trees){int temp=bfs(forest,bx,by,a,b);if(temp==-1){return -1;}//无法砍完所有的树ret+=temp;//累加bx=a,by=b;//更新起点}return ret;}
};

小结

本篇关于bfs算法求取最短路径的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！