用队列解决迷宫问题

《用队列解决迷宫问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#includeconstintm=12;constintp=15;intmaze[m+2][p+2]={{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},//1{0,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},//2{1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},//3{1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},//4{1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},

2、//5{1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1},//6{1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},//7{1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},//8{1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1},//9{1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},//10{1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1},//11{1,0,0,1,1,1,1,1,0

3、,0,0,1,1,1,1,0,1},//12{1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,0},//13{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},//14};structposition{intx,y;};ostream&operator<<(ostream&os,position&m){returnos<<"("<

4、,{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};classlinknode{public:positiondata;linknode*link;linknode(position&x){link=NULL;data=x;}//构造函数};classlinkedqueue{linknode*front,*rear;public:linkedqueue(){front=rear=NULL;}~linkedqueue(){makeempty();}voidenqueue(posi

5、tionx){if(front==NULL)front=rear=newlinknode(x);else{rear->link=newlinknode(x);rear=rear->link;}}voiddequeue(position&x){linknode*p;p=front;x=p->data;front=front->link;deletep;}voidmakeempty(){linknode*p;while(front!=NULL){p=front;front=front->link;deletep;

6、}}boolisempty(){if(front==NULL)returntrue;}};boolfindpath(positionstart,positionfinish){positionhere,nbr;here.x=start.x;here.y=start.y;maze[start.x][start.y]=2;linkedqueueq;do{for(inti=0;i<8;i++){nbr.x=here.x+move[i].a;nbr.y=here.y+move[i].b;if(maze[nbr.x][

7、nbr.y]==0){maze[nbr.x][nbr.y]=maze[here.x][here.y]+1;if(nbr.x==12&&nbr.y==15)break;q.enqueue(nbr);}}if(nbr.x==12&&nbr.y==15)break;if(q.isempty()==true)returnfalse;q.dequeue(here);}while(true);//不要忘记分号intpathlen=maze[finish.x][finish.y]-2;here=finish;for(int

8、j=pathlen-1;j>=0;j--){for(inti=0;i<8;i++){nbr.x=here.x+move[i].a;nbr.y=here.y+move[i].b;if(maze[nbr.x][nbr.y]==j+2){cout<