1 条题解
-
0
C++ :
#include<iostream> #include<cstring> using namespace std; //初始化方向 int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int map[200][200]; int que[10000][3];//队列数组 int pre[10000];//存放前驱节点的数组 int head=0; int tail=1; //递归输出路径 int print(int d){ if(pre[d]!=0){ print(pre[d]); } if(d != tail){ cout<<"("<<que[d][1]<<","<<que[d][2]<<")"<<"->"; }else{ cout<<"("<<que[d][1]<<","<<que[d][2]<<")"<<endl; } } int main(){ int i,j,n,m; cin>>n>>m; for(i = 1;i <= n;i++){ for(j = 1;j <= m;j++){ cin>>map[i][j]; } } int soux,souy;//起点坐标 int desx,desy;//终点坐标 cin>>soux>>souy; cin>>desx>>desy; bool flag=false;//假设没有路径 map[soux][souy]=1;//经过的点设置成1,避免重复 //起点入队 que[tail][1]=soux; que[tail][2]=souy; //起点没有前驱 pre[tail]=0; while(head!=tail){ head++; //循环4个方向 for(int i=0;i<4;i++){ int x=que[head][1]+dx[i]; int y=que[head][2]+dy[i]; //设置边界 if(((x>0)&&(x<=n))&&((y>0)&&(y<=m))&&map[x][y]==0){ tail++; que[tail][1]=x; que[tail][2]=y; pre[tail]=head; //标记该点已经走过 map[x][y]=1; //如果扩展到了目标节点 if((x==desx)&&(y==desy)){ flag=true;//找到了路径 print(tail);//打印路径 break; //跳出当前循环 } } } //如果找到了路径 if(flag==true){ break;//跳出最外层循环 } } //如果没有路径 if(flag==false){ cout<<"no way"<<endl; } }
- 1
信息
- ID
- 422
- 时间
- 1000ms
- 内存
- 120MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者