【刷题22】BFS解决最短路问题

一、边权为1的最短路问题

如图：从A到I，怎样走路径最短

• 一个队列+一个哈希表
• 队列：一层一层递进，直到目的地为止
• 哈希表：记录当前位置是否经过，经过的就不用再进队列
• 为什么可以使用BFS？因为每条边的长度为1，同样的速率走，走相同的步频，谁先到目的地，谁的路径就是最短的

二、迷宫中离入口最近的出口

题目：

思路：BFS+哈希表 找最短路径

• 能到边界，返回ret，ret是层数
• 不能到边界，队列层序结束，返回-1
• 必须是某个位置的上下左右为边界才符合条件，即使刚开始就在边界也不行，也必须要移动，移动到另一个边界上才算；否则队列循环结束也是返回-1，参考示例2和示例3

代码：

class Solution {
public:int bx[4] = {-1,1,0,0};int by[4] = {0,0,-1,1};bool hash[100][100] = {false};int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int n = maze.size();int m = maze[0].size();int ret = 0;queue<pair<int, int>> q;q.push({entrance[0], entrance[1]});while(!q.empty()){int k = q.size();ret++;// 一层的个数while(k--){int x1 = q.front().first;int y1 = q.front().second;// 防止重复if(hash[x1][y1]){q.pop();continue;}for(int i=0; i<4; i++){int x2 = x1+bx[i];int y2 = y1+by[i];if(x2>=0&&x2<n&&y2>=0&&y2<m&&maze[x2][y2]=='.'&&!hash[x2][y2]){if(x2==0 || x2==n-1 || y2==0 || y2==m-1){return ret;}q.push({x2, y2});}}// 标记经过的位置 更新队列hash[x1][y1] = true;q.pop();}}return -1;}
};

三、最小基因变化

题目：

题目理解：

• 一次变化相当于步数，所以可以用BFS
• 最终要变化成的基因序列必须是基因库中存在的，否则返回-1
• 每一次的变化，也必须是在基因库中存在的，否则返回-1

思路：BFS+哈希表

• 两个哈希表，一个标记基因库中有的基因序列，后续要使用（判断每次变化是否在基因库中）；另一个标记是否已经出现过，防止重复
• start字符串与end字符串相同，直接返回0
• end字符串不在基因库中，直接返回-1
• BFS：一个队列，层序遍历，一层就是一次变化
• 基因序列如何变化？题目是字符串有8个字符，所以每个位置的字符变化一次，变化的字符有4个：ACGT
• 只要在基因库中存在并且没有出现过，就入队列，如果该字符串与end字符串相同，就直接返回ret
• 细节：变化前（内循环外面），先用一个临时字符串代替，这样保证只修改了一次；否则变化到后面，前面的也都变化了，就不止修改了一次
• 队列层序完，没有end字符串等于tmp(变化的字符串)，就说明start字符串变化不到end字符串，最终返回-1

代码：

class Solution {
public:int minMutation(string startGene, string endGene, vector<string>& bank) {unordered_map<string, int> hash; // 标记基因库中出现过的for(auto &e : bank) hash[e]++;unordered_map<string, int> vis; // 标记每次变化是否出现过 防止重复// 如果刚开始就相同if(startGene == endGene) return 0;// endGene不在基因库中if(hash[endGene] == 0) return -1;// 变化的字符string change = "ACGT";queue<string> q;int ret = 0; // 层数就是变化次数q.push(startGene);while(!q.empty()){int k = q.size();ret++;while(k--){string t = q.front();// 获取队列头vis[t]++;// 标记已经出现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[tmp] > 0 && vis[tmp] == 0){q.push(tmp);// 等于最终的字符串 返回if(tmp == endGene){return ret;}}}}}}return -1;}
};

四、单词接龙

题目：

思路：BFS+哈希表

• 本题与上题思路和过程几乎相同，字符=》字符串。以下是不同的地方要注意：
• 都是一次改变，改变的是字符串中的一个字符，上题是ACGT，本题是wordList中出现的单词的所有字符，记得要去重。
• 接下来是用队列完成层序遍历，与上题几乎一样，不同点：取队头元素时，要判断它是否出现过，出现过了就删除队头元素，然后continue（注意：其实加这个是为了避免重复计算，本题如果少了这个条件会超时；上题没有加这个条件并没有超时）；因为wordList中每个单词的长度是一样的，所以外循环是单词的长度（在上题是固定的，为8的字符）；内循环是要变化的字符的个数，就是change字符串(set去重后的)，上题是固定的ACGT，为4个字符。其他是一样的。
• 返回值：不符合条件是返回0；符合条件是返回单词接龙的长度，不是层数，单词接龙的长度就是层数+1，即返回ret+1

代码：

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_map<string, int> hash;for(auto &e : wordList) hash[e]++;unordered_map<string, int> vis;if(beginWord == endWord) return 0;if(hash[endWord] == 0) return 0;// 要变化的字符string str;for (auto& e : wordList){str += e;}set<char> se(str.begin(), str.end());string change(se.begin(), se.end());//queue<string> q;int ret = 0;q.push(beginWord);while(!q.empty()){int k = q.size();ret++;while(k--){string t = q.front();if(vis[t] > 0){q.pop();continue;}vis[t]++;q.pop();for(int i=0; i<wordList[0].size(); i++){string tmp = t;for(int j=0; j<change.size(); j++){tmp[i] = change[j];if(hash[tmp] > 0 && vis[tmp] == 0){q.push(tmp);if(tmp == endWord){return ret+1;}}  }}}}return 0;}
};

五、为高尔夫比赛砍树

题目：

思路：BFS+哈希表

• 把二维数组中所有大于1的元素排序，每次找的元素根据排序从小到大，如上图所示，找一次相当于找一个树的最短路径，所以本题等价于多个迷宫找出口
• 注意：是要找最小的树，然后再根据顺序往上找其他树，并不是说一定要从1开始找，因为1是地面，只是上面的栗子刚好起始点就是1；如果1和4交换，千万不能从4开始走到1，再去找2，这是错的；【0，0】是4，或者说不管是多少，直接去找最小的树就行了（上面的栗子最小的树是2）；如果【0，0】起始点就是最小的树，也不影响，代码中有加判断跳过，然后找次小的树(次小的树这时变成最小的树)，剩下找的过程是正常的（总之：开始找最小的树ret开始计算）
• 最后flag的处理问题：只要有走到目标树，就不会经过最后的flag，如果有经过最后的flag，说明无路可走（周围都是围墙），这时就有可能还有树没有砍掉，结果返回-1；但是有一个情况例外，当只剩下一个树了，那它周围也就没有树了，会经过flag，可是这种情况是对的，不能当作错误的情况处理；可以加个条件：下标i 等于gsz时，代表是最后一个树，不进入flag的处理

代码：

class Solution {
public: int ret = 0;// 返回值-步数int flag = 0;// 标记-是否将所有的树砍掉int n, m;// 矩阵行列int gx = 0, gy = 0;// 开始的位置，后面会更新int i = 0;// 下标-从小到大int gsz = 0;// 树的个数int bx[4] = {-1,1,0,0};int by[4] = {0,0,-1,1};int cutOffTree(vector<vector<int>>& forest) {if(forest[gx][gy] == 0) return -1;n = forest.size();m = forest[0].size();vector<int> v;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(forest[i][j] > 1)// 找树{v.push_back(forest[i][j]);}}}sort(v.begin(), v.end());// 从最小的树开始，或者找到最小树int sz = v.size();gsz = sz;// 全局的树的个数while(sz--){bfs(forest, v[i]);if(flag == 1) return -1;// 还有树没有砍完i++;// 到下一个树}return ret;}void bfs(vector<vector<int>>& forest, int tar){if(tar == forest[gx][gy])// 要找的树就是当前位置{return;}// 不是全局的，每次层序要更新(找一个树)bool vis[50][50] = {false};queue<pair<int, int>> q;q.push({gx, gy});while(!q.empty()){int k = q.size();ret++;while(k--){int x1 = q.front().first;int y1 = q.front().second;if(vis[x1][y1])// 防止重复{q.pop();continue;}q.pop();vis[x1][y1] = true;for(int i=0;i<4;i++){int x2 = x1+bx[i];int y2 = y1+by[i];if(x2>=0&&x2<n&&y2>=0&&y2<m&&forest[x2][y2]!=0&&!vis[x2][y2]){q.push({x2, y2});// 找到目标树if(forest[x2][y2] == tar){gx = x2;// 更新，下次就是从该位置开始gy = y2;return;}}}}}if(i != gsz-1) // 最后一个flag = 1;}
};