[广度优先搜索] 离开中山路。
最编程
2024-04-07 16:39:15
...
题目大意
题目描述
爱与愁大神买完东西后,打算坐车离开中山路。 现在爱与愁大神在x1,y1处,车站在x2,y2处。 现在给出一个n×n(n<=1000)的地图,0表示马路,1表示店铺(不能从店铺穿过),爱与愁大神只能垂直或水平着在马路上行进。 爱与愁大神为了节省时间,他要求最短到达目的地距离(a[i][j]距离为1)。你能帮他解决吗?
输入格式
第1行:一个数 n 第2行~第n+1行:整个地图描述(0表示马路,1表示店铺,注意两个数之间没有空格) 第n+2行:四个数 x1,y1,x2,y2
输出格式
只有1行:最短到达目的地距离
输入输出样例
输入 #1
3 001 101 100 1 1 3 3
输出 #1
4
思路
广搜+STL队列 使用结构体变量 Pos 存储坐标 使用二维数组 mp[1001][1001] 存储地图 使用常量数组 dx[] dy[] 存储马可以走的8个方向 使用整形数组 dis[1001][1001]存储最短步数
代码实现
#include<iostream> #include<queue> using namespace std; struct Pos //存储坐标 { int x,y; }; queue <Pos> q; //STL队列 int n,x,y,tx,ty,dis[1001][1001],s_a,s_b,t_a,t_b; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; //四个方向 char mp[1001][1001]; //存储地图 bool vis[1001][1001]; //存储访问情况 int bfs(int sx,int sy) //搜索函数 { q.push((Pos){sx,sy}); //起点加入队列 vis[sx][sy]=true; while(!q.empty()) { x=q.front().x; y=q.front().y; //赋值 q.pop(); //弹出队列 if(x==t_a&&y==t_b) return dis[x][y]; //条件符合,返回答案 for(int i=0;i<4;i++) //枚举四个方向 { tx=x+dx[i]; ty=y+dy[i]; if(tx<=0||tx>n||ty<=0||ty>n) continue; if(mp[tx][ty]=='1'||vis[tx][ty]==true) continue; dis[tx][ty]=dis[x][y]+1; vis[tx][ty]=true; q.push((Pos){tx,ty}); } } return -1; } int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>mp[i][j]; //输入地图 cin>>s_a>>s_b>>t_a>>t_b; cout<<bfs(s_a,s_b); return 0; }
本题难度 普及/提高-
原文地址:https://www.cnblogs.com/yjhqinghua/p/11395287.html
上一篇: HTTP 414 状态代码