写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：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 #include #include #include #include using namespace std; const int N = 1010; //存坐标 typedef pair PII; int n; int x1, y1, x2, y2; //记录路径和 int dist[N][N]; //存地图 char g[N][N]; queue q; //存偏移量 int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; int bfs(int x1, int y1) { //将dist初始化为-1 memset(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]; } } //如果走不到终点，返回-1 return -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 ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
