首页 > 代码库 > 迷宫探索
迷宫探索
/* 5 4 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 4 3 */ #include<iostream> using namespace std; struct node { int x;//横坐标 int y;//纵坐标 int f;//父亲在队列中的编号 int s;//步数 }; int main() { node que[2051]; int a[51][51]={0}; int book[51][51]={0}; //定义一个用于表示走的方向的数组 int next[4][2]={{0,1},//向右走 {1,0},//向下走 {0,-1},//向左走 {-1,0}};//向上走 int head,tail; int i,j,k,n,m,startx,starty,p,q,tx,ty,flag; cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } cin>>startx>>starty>>p>>q; //队列初始化 head=1; tail=1; //往队列插入迷宫入口坐标 que[tail].x=startx; que[tail].y=starty; que[tail].f=0; que[tail].s=0; tail++; book[startx][starty]=1; flag=0;//用来标记是否到达目标地点,0表示临时没有到达.1表示到达 //当队列不为空的时候循环 while(head<tail) { //枚举4个方向 for(k=0;k<=3;k++) { tx=que[head].x+next[k][0]; ty=que[head].y+next[k][1]; //推断是否越界 if(tx<1||tx>n||ty<1|ty>m) continue; //推断障碍物是否在路上 if(a[tx][ty]==0&&book[tx][ty]==0) { book[tx][ty]=1; que[tail].x=tx; que[tail].y=ty; que[tail].f=head; que[tail].s=que[head].s+1; tail++; } if(tx==p&&ty==q) { flag=1; break; } } if(flag==1) break; head++; } //打印队列中末尾最后一个点(目标点)的步数 //注意tail是指向队列队尾(即最后一位)的下一个位置,所以这须要-1 cout<<que[tail-1].s<<endl; return 0; }
迷宫探索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。