算法笔记（十三）——BFS 解决最短路问题

BFS 解决最短路问题

BFS(广度优先搜索) 是解决最短路径问题的一种常见算法。在这种情况下，我们通常使用BFS来查找从一个起始点到目标点的最短路径。

---

迷宫中离入口最近的出口

题目：迷宫中离入口最近的出口

思路

图论中边路权值为1的情况，利用层序遍历来解决是最经典的做法。
从起点开始层序遍历，在遍历的过程中记录当前遍历的层数。

C++代码

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();vector<vector<bool>> visited(m, vector<bool>(n, false));int ret = 0; queue<pair<int, int>> q;  q.push({entrance[0], entrance[1]});visited[entrance[0]][entrance[1]] = true;while(q.size()){ret++;int sz = q.size();for(int i = 0; i < sz; i++){auto [a, b] = q.front(); q.pop();for(int k = 0; k < 4; k++){int x = a + dx[k], y = b + dy[k];if(0 <= x && x < m && 0 <= y && y < n && maze[x][y] == '.' && !visited[x][y]){if(x == 0 || x == m - 1 || y == 0 || y == n - 1) return ret;q.push({x, y});visited[x][y] = true;}}}}return -1;}
};

最小基因变化

题目：最小基因变化

思路

转化成边路权值为1的图论问题

• 用unordered_set<string> hash(bank.begin(), bank.end());来存储基因库，快速判断该基因是否存在于基因库

• 枚举出的每一个位置，我们先判断其是否为合法基因（如果基因库中有并且该基因没有被访问）

• 用一个unordered_set<string> visited;用于标记是否访问过该基因序列

• 用BFS，尝试每个位置可能变异后得结果，如果变异后的基因是合法基因，就加入队列中，并标记为已访问

C++代码

class Solution 
{
public:int minMutation(string startGene, string endGene, vector<string>& bank) {unordered_set<string> hash(bank.begin(), bank.end()); // 创建一个hash方便判断该基因序列是否合法unordered_set<string> visited; // 用于标记是否访问过该基因序列string change = "ACGT"; // 可能的基因变异字符if(startGene == endGene) return 0; // 起始基因和目标基因相同，不用改变if(!hash.count(endGene)) return -1; // 目标基因不在基因库，返回-1queue<string> q;q.push(startGene); // 起始基因入队visited.insert(startGene); // 标记起始基因被访问int ret = 0;while(!q.empty()){int sz = q.size();ret++;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++) // 每个位置更改 4 次{tmp[i] = change[j];// 如果基因库中有并且该基因没有被访问，则为合法基因if(hash.count(tmp) && !visited.count(tmp)) {// 合法基因等于目标基因返回结果if(tmp == endGene)return ret;// 合法基因入队并且标记访问过了q.push(tmp);visited.insert(tmp);}}}}}return -1;}
};

单词接龙

题目：单词接龙

思路

和上一题的思路一毛一样，只不过上题每个位置变化只有四种可能，而这题每个位置的变换有二十六种可能性

C++代码

class Solution 
{
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> visited; // 记录该单词是否访问过了unordered_set<string> hash(wordList.begin(), wordList.end());if (beginWord == endWord) return 1; // 起始单词和目标单词相同，不用改变if (!hash.count(endWord)) return 0; // 目标单词不在wordList，返回 0 queue<string> q;q.push(beginWord); // 起始单词入队visited.insert(beginWord); // 标记起始单词被访问int ret = 1;while(!q.empty()){ret++;int sz = q.size();while(sz--){string t = q.front();q.pop(); for(int i = 0; i < t.size(); i++) // 遍历单词的每个位置{string tmp = t;for(char ch = 'a'; ch <= 'z'; ch++) // 每个位置更改 26 次{tmp[i] = ch;// 判断是否为合法单词if(hash.count(tmp) && !visited.count(tmp)){if (tmp == endWord) return ret;q.push(tmp);visited.insert(tmp);}}}}}return 0;}
};

为高尔夫比赛砍树

题目：为高尔夫比赛砍树

思路

其实本题就是多次的迷宫问题累计求和，不停的变换起始位置(x, y)以及终止位置(nx, ny)

• 遍历森林，将树木的位置加入 trees数组中
• 树木的高度进行排序
• 用BFS计算起始位置(x, y)以及终止位置(nx, ny)的距离
• 累加步数，并更新起始位置(x, y)

C++代码

class Solution 
{int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;bool visited[51][51];int bfs(vector<vector<int>>& forest, int x, int y, int nx, int ny) {if (x == nx && y == ny) return 0;  // 如果起始位置和目标位置相同，步数为0queue<pair<int, int>> q;memset(visited, 0, sizeof visited);q.push({x, y});visited[x][y] = true;int ret = 0;while(!q.empty()){   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(0 <= x && x < m && 0 <= y && y < n && forest[x][y] && !visited[x][y]){if (x == nx && y == ny) // 如果到达目标位置，返回步数return ret;q.push({x, y});visited[x][y] = true;}}}}return -1;}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});// 根据树木的高度进行排序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 x = 0, y = 0; // 起始位置(0, 0)int ret = 0;// 从小到大遍历for(auto& [nx, ny] : trees){int step = bfs(forest, x, y, nx, ny);if(step == -1) return -1;ret += step;x = nx, y = ny; // 更新起始位置}return ret;}
};