解题思路:利用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++代码)(第11位大于1.5才能进位)浏览:1152 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:605 |
C语言考试练习题_排列 (C++代码)浏览:639 |
大神老白 (C语言代码)浏览:715 |
震宇大神的杀毒软件 (C语言代码)浏览:1253 |
川哥的吩咐 (C语言代码)浏览:877 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:570 |
简单的a+b (C语言代码)浏览:551 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:1251 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:339 |