中山企业手机网站建设,手机网站建设的趋势,wordpress大型站点,最近三天的新闻热点目录
写在前面#xff1a;
题目#xff1a;P1746 离开中山路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述#xff1a;
输入格式#xff1a;
输出格式#xff1a;
输入样例#xff1a;
输出样例#xff1a;
解题思路#xff1a;
代码#xff1a; …目录
写在前面
题目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 pairint, int PII;int n;
int x1, y1, x2, y2;//记录路径和
int dist[N][N];//存地图
char g[N][N];queuePII 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 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。
