【算法专题十五】BFS解决最短路问题

1.最短路问题简介（边权为1的最短路问题）

2.迷宫中离入口最近的出口

2.1 题目

题目链接

2.2 思路

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>& entrance) {int m = maze.size(), n = maze[0].size();bool vis[m][n];memset(vis, 0, sizeof vis);queue<pair<int, int>> q;q.push({entrance[0], entrance[1]});vis[entrance[0]][entrance[1]] = true;int step = 0;while(q.size()){int sz = q.size();step++;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;}
};

3.最小基因变化

3.1 题目

题目链接

3.2 思路

3.3 代码

class Solution {
public:int minMutation(string startGene, string endGene, vector<string>& bank) {if(startGene == endGene) return 0;unordered_set<string> hash(bank.begin(), bank.end());if(!hash.count(endGene)) return -1;unordered_set<string> vis;string change = "ACGT";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;vis.insert(tmp);q.push(tmp);}}}}}return -1;}
};

4.单词接龙

4.1 题目

题目链接

4.2 思路

4.3 代码

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> hash(wordList.begin(), wordList.end());if(!hash.count(endWord)) return 0;unordered_set<string> vis;queue<string> q;q.push(beginWord);vis.insert(beginWord);int ret = 1;while(q.size()){ret++;int sz = q.size();while(sz--){int sz2 = beginWord.size();string t = q.front();q.pop();for(int i = 0; i < sz2; 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;}
};

5.为高尔夫比赛砍树

5.1 题目

题目链接

5.2 思路

5.3 代码

class Solution {int m, n;
public:int cutOffTree(vector<vector<int>>& f) {m = f.size(), n = f[0].size();// 1. 准备工作：找出砍树的顺序vector<pair<int, int>> tree;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(f[i][j] > 1) tree.push_back({i, j});}}sort(tree.begin(), tree.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] : tree){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];int 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;}
};