【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（12）
目录
写在前面：
题目：P1746 离开中山路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述：
输入格式：
输出格式：
输入样例：
输出样例：
解题思路：
代码：
AC ！！！！！！！！！！
写在最后：
写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：P1746 离开中山路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述：
输入格式：
第 1 行包含一个数 n。
第 2 行到第 n + 1 行：整个地图描述
（00 表示马路，11 表示店铺，注意两个数之间没有空格）。
第 n + 2 行：四个数 x1, y1, x2, y2。
输出格式：
只有 11 行，即最短到达目的地距离。
输入样例：
3
001
101
100
1 1 3 3输出样例：
4解题思路：
这道题也是一道基础的迷宫问题，
我们用搜索来做，然后观察一下他的数据范围，
地图1000乘1000的大小，
很明显dfs会超时，所以这道题需要使用bfs进行搜索，
我们先来看一下地图的样例，模拟一下：
我们从坐标1,1开始：
然后直接往四个方向搜索即可：
一直搜索到目标终点：
所以最后返回的最短路径就是4，
那么其实我们可以发现，题目中有个求最短路径的这个字眼，
我们可以判断这道题多半是个bfs的题目。
根据这个思路，我们开始实现代码：
代码：
//包好头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;const int N = 1010;//存坐标
typedef pair<int, int> PII;int n;
int x1, y1, x2, y2;//记录路径和
int dist[N][N];//存地图
char g[N][N];queue<PII> q;//存偏移量
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};int bfs(int x1, int y1)
{//将dist初始化为-1memset(dist, -1, sizeof(dist));q.push({x1, y1});//起点dist[x1][y1] = 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 > n) continue;if(dist[a][b] >= 0) continue;if(g[a][b] != '0') continue;q.push({a, b});//记录路径和dist[a][b] = dist[t.first][t.second] + 1;//如果到终点了，就直接返回终点值if(dist[x2][y2] > 0)return dist[x2][y2];}}//如果走不到终点，返回-1return -1;
}int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%s", g[i] + 1);}scanf("%d %d %d %d", &x1, &y1, &x2, &y2);int res = bfs(x1, y1);printf("%d", res);return 0;
}
AC ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
