目录
原理剖析：
1、 1926. 迷宫中离入口最近的出口
2、 433. 最小基因变化
3、 127. 单词接龙
4、 675. 为高尔夫比赛砍树
原理剖析：
为什么BFS能够解决最短路径问题？
对于无权图(边权为1)或所有边权重相等的情况，BFS是一种有效的最短路径解决方案。
BFS（广度优先搜索）之所以能够解决最短路径问题，主要是因为它按照从近到远的顺序探索所有的顶点。具体来说，BFS有以下几个特点使其适用于求解最短路径问题：
-
分层搜索：BFS会首先探索起点的所有邻接点，即距离为1的顶点。然后再探索这些顶点的邻接点，即距离为2的顶点，以此类推。这种分层的搜索保证了当我们第一次到达任何一个顶点时，我们找到的就是从起点到该顶点的最短路径。
-
无需权重：在无权图中，所有边的长度被视为相同（通常为1）。因此，BFS通过探索相邻的所有顶点，自然而然地找到了最短路径。
-
队列的使用：BFS使用队列来存储待探索的顶点，这保证了顶点是按照它们被发现的顺序进行探索的，即先入先出的顺序，这也是保持层级顺序和找到最短路径的关键。
由于BFS是逐层探索的，当你第一次到达任何顶点时，你肯定是通过最少数量的边到达的。换句话说，你找到的是从起点到该顶点的最短路径（在无权图中即最少步数）。
-
初始层（距离为0）：首先探索起点本身。这可以被看作是第0层，因为它距离起点的距离为0。
-
第一层（距离为1）：接下来，探索所有直接与起点相邻的顶点。这些顶点构成了第一层，因为你必须经过一条边才能从起点到达这些顶点。
-
第二层（距离为2）：然后，从第一层的顶点出发，探索与它们相邻但尚未被探索的顶点。这些新探索到的顶点构成了第二层，因为从起点到这些顶点需要经过两条边。
-
以此类推：这个过程会继续进行，每次从最新发现的层的顶点出发，探索下一层的顶点。
这种分层的探索方法是BFS能够找到最短路径的关键。因为BFS从起点开始，先探索所有最近的顶点（一步可以到达的），然后是次近的（两步可以到达的），依此类推，所以当它第一次到达一个新顶点时，路径长度（或步数）必定是最小的。
1、 1926. 迷宫中离入口最近的出口
思路：我们采用层序遍历（也称为广度优先搜索，BFS）的方法。这种方法不仅适用于迷宫探索，还能帮助我们找到从入口到最近出口的最短路径。BFS使用队列逐层搜索，vis数组记录是否被访问过，step统计步数。
class Solution {
public:
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int m = maze.size(), n = maze[0].size();
bool vis[m][n];
memset(vis, false, sizeof vis);
queue<pair<int, int>> q;
q.push(make_pair(entrance[0], entrance[1]));
vis[entrance[0]][entrance[1]] = true;
int step = 0;
while (!q.empty()) {
step++;
int sz = q.size();
for (int i = 0; i < sz; i++) {
auto a = q.front();
q.pop();
for (int j = 0; j < 4; j++) {
int x = a.first + dx[j], y = a.second + 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(make_pair(x, y));
vis[x][y] = true;
}
}
}
}
return -1;
}
};-
初始化：首先，我们需要一个访问标记数组
vis来记录哪些位置已经被访问过，防止重复访问造成无限循环。同时，创建一个队列q用于存放待探索的迷宫格子。 -
开始探索：将入口位置入队，并标记为已访问。
-
步数增加：每次开始一轮队列中所有位置的探索，步数增加1，这代表从入口开始，每一步移动都在寻找可能的出口。
-
层序遍历：进行宽度优先搜索，每一轮循环对队列中的所有位置进行探索，对于每一个位置，尝试向上、下、左、右四个方向移动。
- 如果移动后的新位置在迷宫内、是空格子（'.'），并且之前未被访问过，则检查这个新位置是否是出口。出口的定义是位于迷宫边界上的空格子，但不包括入口位置。如果是出口，直接返回当前的步数（即从入口到这个出口的最短路径长度）。
- 如果新位置不是出口，则将其加入队列中，以便进一步的探索，并标记为已访问。
-
无法到达出口：如果队列为空，即所有可达的位置都已被探索过，仍然没有找到出口，则说明无法从入口到达任何出口，返回 -1。
2、 433. 最小基因变化
思路：我们可以把每个基因序列看作是图中的一个顶点，而每次基因的变化则相当于图中两个顶点之间的一条边。这样，问题就转变成了寻找从起始顶点（start 基因序列）到目标顶点（end 基因序列）的最短路径问题，其中每次路径上的移动代表一个基因的变化。
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);
int ret = 0;
string ch = "ACGT";
while (!q.empty()) {
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] = ch[j];
if (hash.count(tmp) && !vis.count(tmp)) {
if (tmp == endGene)
return ret;
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return -1;
}
};-
初始化：创建一个访问集合
vis来记录已经访问过的基因序列，以及一个哈希集合hash来存储基因库中所有有效的基因序列。这样可以快速判断一个基因序列是否有效。 -
特殊情况处理：如果起始基因序列与目标基因序列相同，则不需要进行任何变化，直接返回 0。如果目标基因序列不在基因库中，说明无法通过变化达到目标，返回 -1。
-
BFS 开始：从起始基因序列开始进行宽度优先搜索。每一次搜索的过程中，尝试改变当前基因序列的每一个位置为 'A'、'C'、'G'、'T' 中的任意一个，生成新的基因序列。
-
有效性和目标检查：对于每一个生成的新基因序列，如果它是有效的（即在基因库中）并且之前没有被访问过，则检查它是否为目标基因序列。如果是，那么当前的变化次数就是所求的最少变化次数；如果不是，就将其加入到队列中，以便进一步的搜索。
-
继续搜索直到找到解：重复步骤 3 和 4，直到找到目标基因序列或者搜索结束。每遍历完一层，变化次数加一。
-
返回结果：如果能找到目标基因序列，返回所需的最少变化次数；否则，说明无法通过变化达到目标，返回 -1。
3、 127. 单词接龙
思路：与第二题“433. 最小基因变化”方法等同。
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.push(beginWord);
vis.insert(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.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return 0;
}
};4、 675. 为高尔夫比赛砍树
思路：首先需要找到砍树的顺序，然后按照砍树的顺序，⼀个⼀个的⽤ bfs 求出最短路即可。
class Solution {
public:
int m, n;
int cutOffTree(vector<vector<int>>& forest) {
vector<pair<int, int>> trees;
m = forest.size(), n = forest[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (forest[i][j] > 1)
trees.push_back(make_pair(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, by = 0, ret = 0;
for (auto& a : trees) {
int step = bfs(forest, bx, by, a.first, a.second);
if (step == -1)
return -1;
ret += step;
bx = a.first, by = a.second;
}
return ret;
}
vector<vector<bool>> vis;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int bfs(vector<vector<int>> forest, int bx, int by, int ex, int ey) {
if (bx == ex && by == ey)
return 0;
vector<vector<bool>> vis(m, vector<bool>(n, false));
queue<pair<int, int>> q;
q.push(make_pair(bx, by));
vis[bx][by] = true;
int step = 0;
while (q.size()) {
step++;
int sz = q.size();
while (sz--) {
auto a = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x = a.first + dx[i], y = a.second + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && forest[x][y] &&
!vis[x][y]) {
if (x == ex && y == ey)
return step;
q.push(make_pair(x, y));
vis[x][y] = true;
}
}
}
}
return -1;
}
};
