解题思路:利用BFS解决最短路径
参考代码: #include <iostream> using namespace std; struct note{ int x; //横坐标 int y; //纵坐标 int step; //保存当前步数 }Que[10001]; int main(){ int count; cin>>count; while(count){ int m,n,tail,head,flag=0,book[101][101]={0}; char Start_x,Start_y,End_x,End_y,map[101][101]={0}; cin>>n>>m; int tx,ty,k; int next[4][2]={{1,0}, //向下走 {0,1}, //向右走 {-1,0}, //向上走 {0,-1}};//向左走 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>map[i][j]; if(map[i][j]=='S') Start_x=i,Start_y=j; else if(map[i][j]=='E') End_x=i,End_y=j; } head=1; tail=1; Que[tail].x=Start_x; Que[tail].y=Start_y; Que[tail].step=0; tail++; book[Start_x][Start_y]=1; while(head<tail){ for(k=0;k<=3;k++){ tx=Que[head].x+next[k][0]; ty=Que[head].y+next[k][1]; if(tx<1||ty<1||tx>n||ty>m) continue; if(map[tx][ty]!='#'&&book[tx][ty]==0){ book[tx][ty]=1; Que[tail].x=tx; Que[tail].y=ty; Que[tail].step=Que[head].step+1; tail++; } if(tx==End_x&&ty==End_y){ flag=1; break; } } if(flag) break; head++; } if(flag==1) cout<<Que[tail-1].step<<endl; else cout<<"-1"<<endl; count--; } return 0; }
深搜超时版:
#include <iostream> using namespace std; int Min=99999; char Map[101][101]; int book[101][101],m,n; int Start_x,Start_y,End_x,End_y; void Dfs(int x,int y,int step){ if(x==End_x&&y==End_y){ if(step<Min) Min=step; //更换最小步数 return; } int tx,ty,k; int next[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; /* 枚举4个方向 */ for(k=0;k<=3;k++){ tx=x+next[k][0]; ty=y+next[k][1]; if(tx<1||tx>n||ty<1||ty>m) continue; if(Map[tx][ty]!='#'&&book[tx][ty]==0){ book[tx][ty]=1; Dfs(tx,ty,step+1); book[tx][ty]=0; } } return; } int main(){ int count; cin>>count; while(count--){ cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>Map[i][j]; if(Map[i][j]=='S') Start_x=i,Start_y=j; //保存初始位置 else if(Map[i][j]=='E') End_x=i,End_y=j; //保存最终位置 } book[Start_x][Start_y]=1; Dfs(Start_x,Start_y,0); if(Min) cout<<Min<<endl; else cout<<"-1"<<endl; } return 0; }
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题8.2 (C语言代码)浏览:5262 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:933 |
一元一次方程 (C语言代码)浏览:4188 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:587 |
快速排序算法1浏览:993 |
C语言训练-斐波纳契数列 (C语言代码)浏览:536 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:465 |
1074题 初学者,求帮忙看下,不知道哪错了浏览:295 |
P1003 (Java代码)浏览:777 |
【数组的距离】 (C语言代码)浏览:542 |