刷题训练之解决最短路径问题
> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。> 目标：熟练解决最短路径问题算法。
> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。
> 专栏选自：刷题训练营
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：
⭐知识讲解
基本思想：
- 采用 dfs 解决问题
🌙topic-->1
题目链接：1. - 力扣（LeetCode）
题目分析：
给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
算法原理：
- 解法：采用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>& e) {
int m = maze.size(), n = maze[0].size();
bool vis[m][n];
memset(vis, 0, sizeof vis);
queue<pair<int, int>> q;
q.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;
}
};🌙topic-->2
题目链接：2. - 力扣（LeetCode）
题目分析：
基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
- 例如，
"AACCGGTT" --> "AACCGGTA"就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
算法原理：
- 解法：采用BFS算法
图解：
代码演示：
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);
vis.insert(tmp);
}
}
}
}
}
return -1;
}
};🌙topic-->3
题目链接：3. - 力扣（LeetCode）
题目分析：
字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
- 每一对相邻的单词只差一个字母。
- 对于
1 <= i <= k时，每个si都在wordList中。注意，beginWord不需要在wordList中。 sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
算法原理：
- 解法：采用BFS算法
图解：
跟上面解法是一样的，这里就是不再赘述了。
代码演示：
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;
}
};🌙 topic-->4
题目链接：4. - 力扣（LeetCode）
题目分析：
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
0表示障碍，无法触碰1表示地面，可以行走比 1 大的数表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
算法原理：
- 解法：采用BFS算法
图解：
代码演示：
class Solution {
int m, n;
public:
int cutOffTree(vector<vector<int>>& f) {
m = f.size(), n = f[0].size();
// 1. 准备⼯作：找出砍树的顺序
vector<pair<int, int>> trees;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (f[i][j] > 1)
trees.push_back({i, j});
sort(trees.begin(), trees.end(),[&](const pair<int, int>& p1, const pair<int, int>& p2) {
return f[p1.first][p1.second] < f[p2.first][p2.second];
});
// 2. 按照顺序砍树
int bx = 0, by = 0;
int ret = 0;
for (auto& [a, b] : trees) {
int step = bfs(f, 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>>& f, 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); // 清空之前的数据
q.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 && f[x][y] &&
!vis[x][y]) {
if (x == ex && y == ey)
return step;
q.push({x, y});
vis[x][y] = true;
}
}
}
}
return -1;
}
};🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
原文地址：https://blog.csdn.net/AAlykk/article/details/142719801
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！