0.原理讲解

• 最短路径是图里的常见问题
• 本专题主要讲解边权为一的最短路问题
  • 边权全都相同即可，并非只能为一
• 方法：从起点开始，来一次BFS即可
• 如何找出最短路径是多长呢？
  • 拓展的层数，就是最短路的长度
    

---

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

1.题目链接

• 迷宫中离入口最近的出口

---

2.算法原理详解

• 思路：BFS
  • 从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数
    • 这样就能在找到出⼝的时候，得到起点到出⼝的最短距离
  • BFS解决迷宫问题，是最经典的做法

---

3.代码实现

class Solution 
{int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};
public:int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int n = maze.size(), m = maze[0].size();vector<vector<bool>> visit(n, vector<bool>(m, false));visit[entrance[0]][entrance[1]] = true;queue<pair<int, int>> q;q.push({entrance[0], entrance[1]});// BFSint 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], y = b + dy[i];if(x >= 0 && x < n && y >= 0 && y < m \&& maze[x][y] == '.' && !visit[x][y]){// 判断是否遇到出口if(x == 0 || x == n - 1 || y == 0 || y == m - 1){return step;}visit[x][y] = true;q.push({x, y});}}}}return -1;}
};

---

2.最小基因变化

1.题目链接

• 最小基因变化

---

2.算法原理详解

• 分析：如果将「每次字符串的变换」抽象成图中的「两个顶点和⼀条边」的话，问题就变成了「边权为 1 的最短路问题」

• 问题为什么可以这样转化成「边权为 1 的最短路问题」？

  • 从源字符串变到目标字符串，可以抽象成从起点到终点
  • 中间的每一次变换，都可以抽象成图中的「两个顶点和⼀条边」
  • 每次都只能变换一个字符，那么可以抽象成两个顶点间，权值均为1
    

• 如何枚举出所有的变化情况呢？

  • 直接暴力枚举每一个位置的每一个变化情况即可

• 枚举出来的所有情况，都需要加入到队列里面吗？

  • 不需要，如果基因库中没有此次变化的结果，那么此次变化就不是一次合法的变化

• 如何快速判断是否在基因库中存在？

  • hash<string>

• 细节：用hash<string>来标记搜索过的状态

---

3.代码实现

int MinMutation(string startGene, string endGene, vector<string>& bank) 
{unordered_set<string> visit; // 用来标记已经搜索过的状态unordered_set<string> hash(bank.begin(), bank.end()); // 存储基因库string change = "ACGT"; // hash// 边界情况处理if(startGene == endGene){return 0;}if(!hash.count(endGene)){return -1;}queue<string> q;q.push(startGene);visit.insert(startGene);// BFSint ret = 0;while(q.size()){ret++;int sz = q.size();while(sz--){string str = q.front();q.pop();// 将下一层入队列// 暴力穷举所有的变化情况:Pfor(int i = 0; i < 8; i++){string tmp = str; // 细节：确保每次只变化一个位置for(int j = 0; j < 4; j++){tmp[i] = change[j];if(tmp == endGene){return ret;}if(hash.count(tmp) && !visit.count(tmp)){visit.insert(tmp);q.push(tmp);}}}}}return -1;
}

---

3.单词接龙

1.题目链接

• 单词接龙

---

2.算法原理详解

• 分析：如果将「每次字符串的变换」抽象成图中的「两个顶点和⼀条边」的话，问题就变成了「边权为 1 的最短路问题」

• 问题为什么可以这样转化成「边权为 1 的最短路问题」？

  • 从源字符串变到目标字符串，可以抽象成从起点到终点
  • 中间的每一次变换，都可以抽象成图中的「两个顶点和⼀条边」
  • 每次都只能变换一个字符，那么可以抽象成两个顶点间，权值均为1
    

• 如何枚举出所有的变化情况呢？

  • 直接暴力枚举每一个位置的每一个变化情况即可

• 枚举出来的所有情况，都需要加入到队列里面吗？

  • 不需要，如果字典中没有此次变化的结果，那么此次变化就不是一次合法的变化

• 如何快速判断是否在字典中存在？

  • hash<string>

• 细节：用hash<string>来标记搜索过的状态

3.代码实现

int LadderLength(string beginWord, string endWord, vector<string>& wordList) 
{unordered_set<string> visit;unordered_set<string> dictionary(wordList.begin(), wordList.end());if(!dictionary.count(endWord)){return 0;}queue<string> q;q.push(beginWord);visit.insert(beginWord);// BFSint count = 0;while(q.size()){count++;int sz = q.size();while(sz--){string str = q.front();q.pop();// 将下一层入队列// 暴力枚举所有可能情况:Pfor(int i = 0; i < beginWord.size(); i++){string tmp = str; // 细节：确保每次只更改一个位置for(char j = 'a'; j <= 'z'; j++){tmp[i] = j;if(dictionary.count(tmp) && !visit.count(tmp)){if(tmp == endWord){return ++count;}q.push(tmp);visit.insert(tmp);}}}}}return 0;
}

---

4.为高尔夫比赛砍树

• 思路：将问题转化为若干个「迷宫问题」-> 从入口找出口
  • 先找出砍树的顺序
  • 然后按照砍树的顺序，⼀个⼀个的⽤BFS求出最短路径即可

class Solution 
{typedef pair<int, int> PII;int n, m;bool visit[50][50];// 方向向量数组int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};
public:int cutOffTree(vector<vector<int>>& forest) {n = forest.size(), m = forest[0].size();// 找出砍树的顺序vector<PII> trees;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(forest[i][j] > 1){trees.push_back({i, j});}}}sort(trees.begin(), trees.end(), [&](const PII& p1, const PII& p2){return forest[p1.first][p1.second] < forest[p2.first][p2.second];});// 按照顺序砍树int ret = 0;int beginX = 0, beginY = 0;for(auto& [a, b] : trees){int step = BFS(forest, beginX, beginY, a, b);if(step == -1){return -1;}ret += step;beginX = a, beginY = b;}return ret;}// 解决单源权值为一的最短路径问题int BFS(vector<vector<int>>& forest, int beginX, int beginY, int endX, int endY){// 边界情况处理if(beginX == endX && beginY == endY){return 0;}memset(visit, false, sizeof visit); // 每次调用BFS都需要执行，否则影响下次BFSvisit[beginX][beginY] = true;queue<PII> q;q.push({beginX, beginY});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], y = b + dy[i];if(x >= 0 && x < n && y >= 0 && y < m \&& forest[x][y] && !visit[x][y]){if(x == endX && y == endY){return step;}visit[x][y] = true;q.push({x, y});}}}}return -1;}
};