解题思路:使用宽度优先搜索,在计算最短路径时采用坐标方式计算d[nextx][nexty]=d[nowx][nowy]+1来更新路径值
注意事项:坐标存储有两种方式pair<int,int>p或者结构体
参考代码:
#include<iostream> #include<queue> using namespace std; const int INF=1000000; char arr[100][100]; int d[100][100];//路径坐标 int n,m,k; int sx,sy,ex,ey;//起终点坐标 int index[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //四个方向 struct Indexnum { int x1; int y1; }; int bfs(Indexnum x) { for(int i=0;i<m;i++)//初始化 { for(int j=0;j<k;j++) { d[i][j]=INF; } } queue<Indexnum>q1; int cnt=0; q1.push(x); d[sx][sy]=0; while(!q1.empty()) { Indexnum p,p1; p=q1.front(); q1.pop(); if(p.x1==ex && p.y1==ey) { break; } for(int i=0;i<4;i++) { int x2=p.x1+index[i][0];//更新坐标 int y2=p.y1+index[i][1]; if(x2>=0 && x2<m && y2>=0 && y2<k && d[x2][y2]==INF&& arr[x2][y2]!='#') { p1.x1=x2; p1.y1=y2; d[x2][y2]=d[p.x1][p.y1]+1;//更新路径长度 q1.push(p1); } } } return d[ex][ey]; } int main() { cin>>n; while(n!=0) { cin>>m>>k; for(int i=0;i<m;i++) { for(int j=0;j<k;j++) { cin>>arr[i][j]; if(arr[i][j]=='S') { sx=i; sy=j; } if(arr[i][j]=='E') { ex=i; ey=j; } } } Indexnum g; g.x1=sx; g.y1=sy; if(bfs(g)==INF)//路径不可达 { cout<<"-1"<<endl; } else { cout<<bfs(g)<<endl; } n--; } return 0; }
0.0分
0 人评分
剪刀石头布 (C语言代码)不知道怎么直接在scanf中用枚举变量浏览:1318 |
求圆的面积 (C语言代码)浏览:1272 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:647 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:1099 |
【偶数求和】 (C语言代码)浏览:567 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:474 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:633 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:550 |
循环入门练习5 (C语言代码)浏览:839 |
小九九 (C语言描述,不看要求真坑爹)浏览:985 |