宽度优先 哈希算法 【算法】使用BFS算法（队列、哈希等）解决最短路径问题（迷宫、基因变化、单词接龙、高尔夫）（C++）

文章目录

1. 前言1.1 什么是最短路问题？1.1.1 什么是权值？

1.2 如何解决此类最短路径？1.3 BFS解最短路径 前提 （FloodFill / 洪流问题）

2. 算法题1926.迷宫中离入口最近的出口433.最小基因变化127.单词接龙675.为高尔夫比赛砍树

1. 前言

1.1 什么是最短路问题？

我们这里主要探讨权值为1的最短路问题。

1.1.1 什么是权值？

而对于权值为1的最短路问题：即不考虑每个路径点的值，只考虑最短的路径是什么即可。

1.2 如何解决此类最短路径？

1.3 BFS解最短路径 前提 （FloodFill / 洪流问题）

关于如何用dfs或bfs算法对二维数组进行搜索，可以看下面的一篇文章：

【算法】bfs与dfs算法解决FloodFill（洪流）问题（C++）

2. 算法题

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

思路

题目分析：本题是一道经典的迷宫问题，我们可以将其转化理解为上图所示。主思路：BFS，我们从起始位置开始，一层一层像外扩（上下左右四个方向都执行扩展）直到扩展到边界（即出口），此时扩展的层数就是最短的路径思路步骤：

创建一个visited数组，用于标记迷宫每位是否走过。创建队列，存储迷宫中每一位的下标（pair类型）将起始位置下标加入到队列中，进行循环，直至队列为空

循环中每次++step，并执行sz次（队列元素个数）扩充，每次扩充即向上下左右四个方向扩。每向一个方向扩后，检查该位置是否为终点。 根据前言中的洪流问题，结合下面的代码理解！

代码

class Solution {

public:

int dx[4] = {0, 0, -1, 1}; // 标记x, y 坐标的四个方向走向

int dy[4] = {-1, 1, 0, 0};

int nearestExit(vector>& maze, vector& entrance) {

int step = 0; // 记录走过的步数

int a = entrance[0], b = entrance[1]; // 提取起始位置坐标

int m = maze.size(), n = maze[0].size();

vector> visit; // 标记是否被遍历过

visit.resize(m, vector(n, false)); // 初始化

visit[a][b] = true;

queue> q; // 存储位置坐标

q.push({a, b});

while(!q.empty())

{

++step;

int sz = q.size(); // 按层遍历当前队中元素

for(int j = 0; j < sz; ++j)

{

auto [_x, _y] = q.front(); // 提取队头元素坐标

q.pop();

for(int i = 0; i < 4; ++i) // 搜索上下左右四个位置

{

int x = _x + dx[i];

int y = _y + dy[i];

if((x < m && x >= 0) && (y < n && y >= 0) && !visit[x][y] && maze[x][y] == '.')

{

// 判断此时是否是终点

if(x == 0 || x == m - 1 || y == 0 || y == n - 1) return step;

q.push({x, y});

visit[x][y] = true;

}

}

}

}

return -1;

}

};

433.最小基因变化

思路

题意分析：通过将字符串startGene 转化为 endGene，且每次变化都在数组bank中存在，求转化的最少次数。 当我们把startGene 转化 求得最终结果endGene时，如下图所示，其本质上属于 边权为1的最路径问题，据此我们有以下思路： 解法：哈希表 + 队列 BFS

代码

对于下面的代码，主要就一处进行解释： 为什么要用临时字符串tmp?

对于两层for循环：每次外层循环只对一个字符进行更改，使用临时字符串tmp，而不对字符串t一直进行更改（比如第一次外层循环AAAA->…->TAAA后，由于更改的是字符串tmp，此时t依然是AAAA，第二次外层循环执行时依然是从AAAA->ACAA开始）

int minMutation(string startGene, string endGene, vector& bank) {

unordered_set visited; // 用于记录所有检索过的状态

unordered_set hash(bank.begin(), bank.end()); // 记录基因库中的所有序列

string change = "ACGT"; // 用于对序列中字符进行更改

// 处理边界情况

if(startGene == endGene) return 0;

if(!hash.count(endGene)) return -1;

queue q; // 创建队列存储满足条件的序列变化

q.push(startGene);

visited.insert(startGene);

int minCount = 0; // 最小变化次数（最终结果）

while(q.size())

{

++minCount;

int sz = q.size();

while(sz--) // 队列大小即为 下一次待变化的序列数

{

string t = q.front(); // 提取当前序列

q.pop();

for(int i = 0; i < 8; ++i) // 每个序列有8个字符，对所有字符进行转化

{

string tmp = t; // 每次循环只对一个字符进行更改，使用临时字符串tmp，使不对t一直进行更改（比如GAAA->TAAA后，继续进）

for(int j = 0; j < 4; ++j) // 每个字符进行"ACGT"四种变化

{

tmp[i] = change[j]; // 更改字符

if(hash.count(tmp) && !visited.count(tmp)) // 此时序列是合法的更改（在bank中）

{

if(tmp == endGene) return minCount; // 此时的合法序列为最终结果，返回

q.push(tmp);

visited.insert(tmp);

}

}

}

}

}

return -1;

}

127.单词接龙

思路

题意分析：这道题与上一道基因变化很类似，代码编写也十分类似，，下面是思路：解法：哈希表 + 队列BFS

题目要求找到 最短转换序列的 最小单词数，而beginWord自身也算一个，则在创建结果变量时我们初始化为1。哈希表：

visited 用于记录所有检索过的单词，使不重复改变hash 标记字典wordList的所有单词 对于两个for循环：

外层循环：通过提取队头字符串，对该单词进行遍历，执行对每一位的更改内层循环：对每一位更改的具体操作，从’a’~‘z’，依次对字符进行替换

代码

int ladderLength(string beginWord, string endWord, vector& wordList) {

unordered_set hash(wordList.begin(), wordList.end());

unordered_set visited;

if(!hash.count(endWord)) return 0;

queue q;

q.push(beginWord);

visited.insert(beginWord);

int minCount = 1; // 首先加上beginWord自身

while(q.size())

{

++minCount;

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(!visited.count(tmp) && hash.count(tmp))

{

if(tmp == endWord) return minCount;

q.push(tmp);

visited.insert(tmp);

}

}

}

}

}

return 0;

}

675.为高尔夫比赛砍树

思路

题意分析：题目要求按照从低到高的顺序砍树，求砍树所走的最小步数。这道题实则是一个对洪流和迷宫问题的结合考研，编写代码时也是如此。对于示例一： 解法：队列BFS主要思路：

利用二维数组存储树的下标，并排序得到砍树的顺序

直接两层循环创建数组，并自定义比较函数排序 执行砍树过程

从起始位置开始，每一小部分（1->2）都进行依次bfs，bfs用于寻找从起始树到目标树的步数。如果其中一个部分无法执行，最终就无法执行 bfs

创建visited与dx、dy全局数组在进行多次 BFS 搜索时，每次搜索的起点和终点都可能不同，因此需要将访问标记数组 visited 重置，以免对下一次搜索结果产生影响。随后利用队列进行bfs的具体步骤，我们在floodfill写过很多，这里不再赘述，看代码就能理解。

代码

class Solution {

public:

int m, n; // 定义全局变量便于访问

int cutOffTree(vector>& forest) {

m = forest.size(), n = forest[0].size();

// 1. 通过容器存储 需要砍的树

vector> 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}); // 大于1的是待砍的树

// 1.5 排序，找出 砍树顺序

sort(trees.begin(), trees.end(), [&](const pair& p1, const pair& p2){

return forest[p1.first][p1.second] < forest[p2.first][p2.second];

});

// 2. 砍树步骤

int bx = 0, by = 0; // 起始位置 坐标

int minCount = 0;

for(auto &[a, b] : trees)

{

// step : 从当前位置到下一位置的步数

int step = bfs(forest, bx, by, a, b); // 后四个参数分别为起始位置的x, y坐标以及目标位置的x, y坐标

if(step == -1) return -1; // 其中一棵树无法砍到，最终就无法砍掉所有的树

minCount += step;

bx = a, by = b; // 更新下一次的起始位置

}

return minCount;

}

bool visited[51][51]; // 用于记录当前位置是否被检索过

int dx[4] = {0, 0, -1, 1}; // 用于x坐标的上下左右方向更新

int dy[4] = {-1, 1, 0, 0}; // 用于y坐标的上下左右方向更新

int bfs(vector> &forest, int beginX, int beginY, int endX, int endY)

{

if(beginX == endX && beginY == endY) return 0;

memset(visited, false, sizeof(visited));

queue> q; // 创建队列用于搜索

q.push({beginX, beginY});

visited[beginX][beginY] = 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], y = b + dy[i];

if((x >= 0 && x < m) && (y >= 0 && y < n) && !visited[x][y] && forest[x][y]) // 在合法范围内对所有未被检索的位置执行：

{

if(x == endX && y == endY) return step;

q.push({x, y});

visited[x][y] = true;

}

}

}

}

return -1;

}

};

好文阅读