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; // 起始位置标记为truewhile(!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);// 走不到直接返回-1if(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;}
};
