1.迷宫中离入口最近的出口
首先我们可以将这道题目简化一下，可以往我们这一章的主题上面来想想。
我们利层序遍历来解决最短路径问题，是最经典的做法。我们可以从起点开始层序遍历, 并组在遍历的过程中记录当前遍历的层数。这样就能在找到出口的时候，得到起点到出口的最短距离，话不多说，我们直接来上思路：
直接上代码：
class Solution {
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
bool vis[101][101] = {false};
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int m = maze.size(); // 横坐标
int n = maze[0].size(); // 纵坐标
int step = 0; // 记录结果
queue<pair<int,int>> q;
q.push({entrance[0],entrance[1]}); // 起始位置进队列
vis[entrance[0]][entrance[1]] = true; // 起始位置标记为true
while(!q.empty())
{
step++;
int sz = q.size();
for(int i = 0; i < sz; i++)
{
auto [a, b] = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int x = a + dx[i];
int y = b + dy[i];
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;
// 判断是否已经到达出⼝
vis[x][y] = true;
q.push({x,y});
}
}
}
}
return -1;
}
};2.最小基因变化
首先我们看到这个题目，真的是难从下手，既然我们这章是最短路径，我们可以尝试从这方面来考虑考虑，我们可以考虑尝试来转化一下哈。
直接上思路：
直接上代码：
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
unordered_set<string> vis; // 用来标记已经搜索过的状态
unordered_map<string,int> hash; // 存储基因库中的字符串
for(auto& e : bank)
hash[e]++;
char change[4] = {'A','C','G','T'};
// 处理边界情况
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--)
{
auto front = q.front();
q.pop();
for(int i = 0; i < front.size(); i++)
{
string tmp = front;
for(int j = 0; j < 4; j++)
{
// front[i] = change[j]; // ???
// 此时我们不能在原字符串上修改,会造成一次修改多个字符
tmp[i] = change[j];
// 判断合法性
// 此时我们修改依然是startGene,但是此时已经标记不进队列
if(hash.count(tmp) && !vis.count(tmp)) // 入队列
{
if(tmp == endGene) return ret;
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return -1;
}
};3.单词接龙
首先看到这个题目可以总结转化两个规律：
⭐从beginWord到endWord每次只能修改一个字符，并且每次中从'a'-'z'中挑选一个进行修改
⭐每次修改的字符串必须在wordList中
所以我们会发现和上面那道题的基本是一模一样的，思路和上面一模一样，唯一的是区别是不是统计步数，而是过程中单词的数量，解决这个也很简单，只需将步数+1即可，直接上代码：
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(beginWord == endWord) return 1;
if(!hash.count(endWord)) return 0;
queue<string> q;
q.push(beginWord);
vis.insert(beginWord);
int ret = 0;
while(q.size())
{
ret++;
int sz = q.size();
for(int i = 0; i < sz; i++)
{
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 + 1;
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return 0;
}
};4.为高尔夫比赛砍树
⭐注意：本题是要求砍树必须从低到高砍掉所有的树
所以这道题目的思路和本章的第一个题目的思路是差不多的思路，只不过本题需要调用多个最短路径的代码即可解决，我们直接来上代码：
class Solution {
bool vis[51][51] = {false};
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int m;
int 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});
// 根据树的长度进行排序 - 从小到大
// 使用lambda进行排序
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 ax = 0, ay = 0; //起始位置
int ret = 0;
for(auto& [a, b] : trees)
{
int step = bfs(forest, ax, ay, a, b);
// 走不到直接返回-1
if(step == -1) return -1;
ret += step;
ax = a;
ay = b;
}
return ret;
}
// 传入起点和终点的坐标，返回最短路径
int bfs(vector<vector<int>>& forest, int ax, int ay, int bx, int by)
{
// 处理边界情况
if(ax == bx && ay == by) return 0;
queue<pair<int,int>> q;
// 注意每次都需要清理vis数组
memset(vis, false, sizeof(vis));
q.push({ax,ay});
vis[ax][ay] = 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];
int y = b + dy[i];
if(x >=0 && x <= m - 1 && y >= 0 && y <= n - 1 && !vis[x][y] && forest[x][y])
{
if(x == bx && y == by) return step;
q.push({x,y});
vis[x][y] = true;
}
}
}
}
return -1;
}
};
