【经典算法】BFS_最短路问题

算法原理：
我们可以从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出⼝的时候，得到起点到出⼝的最短距离。

把题目抽象为：从当前位置出发，到离边界上的那个点的最短路程是多少。

细节/技巧问题：

(1) 人当前所在位置不能当做出口。
(2) 出口：与边界相邻的空格就是出口。
(3) 人在移动时仅需走到出口位置即可，不需要走出迷宫。

代码实现：

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();// 假设进去sz个，要同时出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;else{q.push({x, y});vis[x][y] = true;}}}}}return -1;}
};

算法原理：

如果将每次字符串的变换抽象成图中的两个点和⼀条边的话，问题就变成了边权为1的最短路题。

其他细节/技巧问题：

(1) 原字符串每个字符变化后一定存在相同的，此时要用哈希表来标记搜索的状态，每次变化后都扔进哈希表中。
(2) 如何枚举出所有的变化情况呢？直接两层for循环。
(3) 变化成哪种字符串才能入队列呢？变化后的字符串在基因库中存在时，才队列。所以把基因库里的字符串扔进哈希表中，每次变化后都要判断是否在基因库中。

代码实现：

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;queue<string> q;q.push(startGene);vis.insert(startGene);string change = "AGCT";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;}
};

算法原理：

这道题和第二题基本一模一样，都是把一个字符串变化成目标字符串，唯一不同的是本题统计的是整个过程中单词的个数，其实就是上一题的最小次数+1。

细节/技巧问题：

参考前两题

代码实现：

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(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();while(sz--){string t = q.front();q.pop();for(int i = 0; i < 10; i++){string tmp = t;for(char ch = 'a'; ch <= 'z'; ch++){tmp[i] = ch; // 每次只修改一个字符// 存在列表中并且没有被访问过if(!vis.count(tmp) && hash.count(tmp)){if(tmp == endWord) return ret+1; q.push(tmp);vis.insert(tmp);}}}}}return 0;}
};

算法原理：

这道题目确实很难。
这道题可以抽象成若干个迷宫问题。我们只要计算出从这一棵树到下一棵树的最少步数，再把所有的步数相加，就可以求出砍完所有树的最少步数。所以这里要多次使用bfs算法，写成函数，它的作用是统计两棵树之间的最少步数。

难点/细节/技巧问题：

(1) 树的坐标如何存储。使用vector容器。
(2) 由于要按照高度从低到高开始砍，所以先要把树的高度排升序。
(3) bfs的参数是传起点和终点。

代码实现：

class Solution 
{int m, n;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};public:int cutOffTree(vector<vector<int>>& f) {m = f.size(), n = f[0].size();// 记录树的位置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];});int bx = 0, by = 0; // 起始位置int step = 0;for(auto& [a,b] : trees){// 使用bfs计算两树之间的最短路int ret = bfs(f, bx, by, a, b);if(ret == -1) return -1;step += ret;bx = a, by = b; // 更新下一个位置的坐标}return step;}bool vis[51][51];int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey){if(bx == ex && by == ey) return 0;memset(vis, 0, sizeof(vis)); // 每次计算都要把标记还原queue<pair<int ,int>> q;q.push({bx, by});vis[bx][by] = true;int ret = 0; // 记录每两颗树之间的最短步数while(q.size()){ret++;int sz = q.size();while(sz--){auto[a, b] = q.front();q.pop();for(int k = 0; k < 4; k++){int x = a+dx[k], y = b+dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && f[x][y]){// 判断是否走到终点if(x == ex && y == ey) return ret;q.push({x, y});vis[x][y] = true;}}}}return -1;}
};