BFS 解决边权为1的最短路问题
边权为1的最短路问题
最短路问题：
比如说从D->K，找出最短的那条，其中每条路都是有权值，此篇主要讲解的边权为1的最短路问题。
即边权都是一样的。
解法就是从起点开始，做一次BFS：
- 需要一个队列、一个哈希表（检测是否访问过）
- 起点进入队列，然后哈希表标记
- 弹出队头元素，将队头元素能去的位置，加入队列
- 然后将该层依次元素弹出，弹出时继续加入能去的位置（哈希表检测一下）
- 到终点就停止
BFS为什么能找出最短路径：
简单理解一下，假设有4条路，相当于4个人一起出发，每个人每次都向后移动一个单位（因为权值为1），最先到的那一个，就直接“跳出循环”了。
如何找出最短路径：
拓展的层数，就是最短路的长度
1926. 迷宫中离入口最近的出口
题目链接：1926. 迷宫中离入口最近的出口
题目解析
题目给了我们两个数组：
- 二维数组表示迷宫，
+表示墙（不能走），.表示空格（可以走） - 一维数组：当前起始位置
每次只能往上下左右走一步，遇见墙不能走，让我们求最少走多少步，能走到迷宫（走到就行，不用走出去，没有出口就返回-1）。
矩阵大小为m*n
出口是矩阵的边界位置：
x == 0 || x == m -1 || y == 0 || y == n -1
算法原理
每次走一步，找到最少步数，即可以理解为边权为1的最短路问题
- 每次只能往上下左右走一步
- 遇墙不走，第一次到边界就直接返回
代码实现
class Solution {
public:
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool vis[101][101];
int m = 0;
int n = 0;
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance)
{
int ret = 0;
m = maze.size();
n = maze[0].size();
//memset(vis, 0, sizeof(vis));
queue<pair<int, int>> q;
q.push({entrance[0], entrance[1]});
vis[entrance[0]][entrance[1]] = true;
while(q.size())
{
ret++;
int sz = q.size();
for(int i = 0; i < sz; i++)
{
auto [x, y] = q.front();
q.pop();
for(int k = 0; k < 4; k++)
{
int a = dx[k] + x;
int b = dy[k] + y;
if(a >= 0 && a < m && b >= 0 && b < n && maze[a][b] == '.' && !vis[a][b])
{
if(a == 0 || a == m -1 || b == 0 || b == n -1)
{
return ret;
}
q.push({a, b});
vis[a][b] = true;
}
}
}
}
return -1;
}
};
433. 最小基因变化
题目链接：433. 最小基因变化
题目解析
给我们2个基于序列（字符串）start和end，再给我们一个基因库序列（vector<string>）bank，它们都是由8个字符组成，每个字符都是A、C、G、T其中之一
要我们找出从start 变为 end的最短次数，且每次变化，必须要在基因库能找到对应的。
算法原理
每次只能改变基于序列的一个字符，相当于中间可能会产生很多基因序列，然后才到目标序列。
将起始基于序列抽象成一个点，中间的序列抽象成路径，目标序列也是一个点，这样即转换成了求边权为1的最短路径问题
注意事项：
- 用哈希表标记搜索过的字符串
- 对元素字符串一位一位遍历，修改成
ACGT其中一个，这样即可枚举出所以变化情况 - 枚举出的字符串，符合基因库且为搜索过，加入队列
- 基因库的字符串也丢入哈希表，即可快速判断
代码实现
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank)
{
string s = "ACGT";
unordered_set<string> hash(bank.begin(), bank.end()); //基因库
unordered_set<string> vis; //是否搜索过
if(!hash.count(endGene))
{
return -1;
}
if(startGene == endGene)
{
return 0;
}
queue<string> q;
q.emplace(startGene);
vis.emplace(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] = s[j];
if(hash.count(tmp) && !vis.count(tmp))
{
if(tmp == endGene)
{
return ret;
}
q.emplace(tmp);
vis.emplace(tmp);
}
}
}
}
}
return -1;
}
};
127. 单词接龙
题目链接：127. 单词接龙
题目解析
这题意思和上面一题类似，就不多说了
唯一不一样的是，返回值为变化的单词数量
算法原理
思路也是和上一题一样
代码实现
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(!hash.count(endWord))
{
return 0;
}
queue<string> q;
q.emplace(beginWord);
vis.emplace(beginWord);
int ret = 1; //记录单词个数
while(q.size())
{
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++)
{
tmp[i] = ch;
if(hash.count(tmp) && !vis.count(tmp))
{
if(tmp == endWord)
{
return ret;
}
q.emplace(tmp);
vis.emplace(tmp);
}
}
}
}
}
return 0;
}
};
675. 为高尔夫比赛砍树
题目链接：675. 为高尔夫比赛砍树
题目解析
给我们一个m*n的矩阵：
- 0表示障碍，无法触碰
- 1表示地面，可以行走
>1的表示有树，可以行走，数值表示树的高度
每次一个上下左右移动一步，如果遇到树，可以决定是否砍伐，砍完为1
砍伐树的顺序必须由低向高砍伐，比如说树的高度有3, 2, 6, 4, 5（树的高度都不同，切至少要砍到一棵树），砍伐的顺序必须是2, 3, 4, 5, 6
从下标[0, 0]出发，返回砍完所有树需要走的最小次数
算法原理
这里就求出每次要到达要砍位置的最短距离即可，即转换成了若干个迷宫问题了
这里还需要知道具体路径顺序，采用一个二维数组，记录位置，然后排一下序
代码实现
class Solution {
public:
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int m = 0;
int n = 0;
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 bx = 0;
int by = 0;
int ret = 0;
for(auto& [a, b] : trees)
{
int step = bfs(forest, bx, by, a, b);
if(step == -1) return -1;
ret += step;
bx = a;
by = b;
}
return ret;
}
bool vis[51][51];
int bfs(vector<vector<int>>& f, int begin_x, int begin_y, int end_x, int end_y)
{
if(begin_x == end_x && begin_y == end_y) return 0;
queue<pair<int, int>> q;
memset(vis, 0, sizeof(vis));
q.push({begin_x, begin_y});
vis[begin_x][begin_y] = 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 && y >= 0 && x < m && y < n && f[x][y] && !vis[x][y])
{
if(x == end_x && y == end_y)
{
return step;
}
q.push({x, y});
vis[x][y] = true;
}
}
}
}
return -1;
}
};