【AcWing刷题】蓝桥杯专题突破-广度优先搜索-bfs（11）
目录
写在前面：
题目：844. 走迷宫 - AcWing题库
题目描述：
输入格式：
输出格式：
输入样例：
输出样例：
解题思路：
代码：
AC ！！！！！！！！！！
写在最后：
写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：844. 走迷宫 - AcWing题库
题目描述：
输入格式：
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含 m 个整数（00 或 11），表示完整的二维数组迷宫。
输出格式：
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围：
1 ≤ n, m ≤ 100
输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0输出样例：
8解题思路：
今天，我开始学习广度优先搜索，
如果说深度优先搜索是一直往下搜，触底反弹回溯，再继续搜索出所有情况，
那么广度优先是一层一层的搜索，
简单来说就是就是运用二叉树层序遍历的思想进行搜索，
就比如这道题，走迷宫，我们也可以用深度优先搜索去做，
但是题目要求的数据范围比较大，深度优先会超出时间限制，
所以这个时候就要用到广度优先搜索，
接下来是具体思路：
我们需要从左上角到右下角，
找出他们的最短路径和，
运用广度优先的思想：
开始搜索：
继续往下搜索：
红色的数字1，表示的是该坐标与起点距离是1，
层层记录距离，就能返回最短路径和，
继续搜索：
以此类推：
我们就搜索到了最短的路径和，
那么这是怎么实现的呢？
就是利用队列先进先出的特性，
往下遍历的时候，将下一层的数据全部入队：
然后就让该坐标出队，并将下一层入队：
继续出队，然后入队：
就能够达成我们广度搜索的条件往下搜索，
下面是代码实现：
代码：
//包好常用头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>using namespace std;//用来存坐标
typedef pair<int, int> PII;const int N = 110;int n, m;//队列
queue<PII> q;//用来读入地图
int g[N][N];//用来记录地图状态和层数（离初始位置的距离）
int dist[N][N];//坐标偏移量
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};int bfs(int x, int y)
{//先把状态都置位-1memset(dist, -1, sizeof(dist));q.push({x, y});//起点dist[x][y] = 0;//如果队列不为空，就一直出队搜索while(!q.empty()){//记录队头auto t = q.front();q.pop();for(int i = 0; i < 4; i++){//上下左右搜索int a = t.first + dx[i];int b = t.second + dy[i];//控制边界if(a < 1 || a > n || b < 1 || b > m) continue;if(g[a][b] != 0) continue;//如果走过，就不搜索了if(dist[a][b] > 0) continue;//入队q.push({a, b});//记录的路径和+1dist[a][b] = dist[t.first][t.second] + 1;}}//返回终点的路径和return dist[n][m];
}int main()
{scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){scanf("%d", &g[i][j]);}}int res = bfs(1, 1);printf("%d\\n", res);return 0;
}
AC ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。