当前位置：首页 > news >正文

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（12）

news 2025/8/2 17:08:14

写在前面：

题目：P1746 离开中山路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输出格式：

输入样例：

输出样例：

解题思路：

代码：

AC ！！！！！！！！！！

写在最后：

写在前面：

怎么样才能学好一个算法？

我个人认为，系统性的刷题尤为重要，

所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，

事不宜迟，我们即刻开始刷题！

题目：P1746 离开中山路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

第 1 行包含一个数 n。

第 2 行到第 n + 1 行：整个地图描述

（00 表示马路，11 表示店铺，注意两个数之间没有空格）。

第 n + 2 行：四个数 x1, y1, x2, y2。

输出格式：

只有 11 行，即最短到达目的地距离。

输入样例：

输出样例：

解题思路：

这道题也是一道基础的迷宫问题，

我们用搜索来做，然后观察一下他的数据范围，

地图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;
}