求解迷宫的最短路径问题-数据结构队列

#includeiostreamusingnamespacestd;#defineMaxSize50intmg[10][10]={{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1},};structBox{inti,j,pre;};structQuType{Boxdata[MaxSize];intfront,rear;};voidprint(QuTypequ,intfront){intk=front,j,ns=0;do//反向找到最短的路径，将该路径上的方块的pre成员设置成-1{j=k;k=qu.data[k].pre;qu.data[j].pre=-1;}while(k!=0);cout迷宫路径如下:endl;k=0;while(kMaxSize)//正向搜索到pre为-1的方块，即构成正向的路径{if(qu.data[k].pre==-1){ns++;cout(qu.data[k].i,qu.data[k].j);if(ns%5==0){coutendl;}}k++;}coutendl;}boolmgpath(intxi,intyi,intxe,intye){inti,j,di;//定义下标boolfind=0;QuTypequ;//定义数据类型为QuType的ququ.front=qu.rear=-1;//初始化队头指针和队尾指针qu.rear++;qu.data[qu.rear].i=xi;//把入口坐标赋给顺序队列qu.data[qu.rear].j=yi;qu.data[qu.rear].pre=-1;mg[xi][yi]=-1;//把入口坐标赋值为-1避免重复索引while(qu.front!=qu.rear&&!find)//如果队尾和队头指针不相同且发现新的方向进行循环{qu.front++;//出队但是仍然在队列之中i=qu.data[qu.front].i;//j=qu.data[qu.front].j;if(i==xe&&j==ye)//如果找到出口，就输出路径{find=1;print(qu,qu.front);returntrue;}for(di=0;di4;di++)//循环扫描每个方块的方位，把每个可走的方块插入队列之中{switch(di){case0:i=qu.data[qu.front].i-1;j=qu.data[qu.front].j;break;case1:i=qu.data[qu.front].i;j=qu.data[qu.front].j+1;break;case2:i=qu.data[qu.front].i+1;j=qu.data[qu.front].j;break;case3:i=qu.data[qu.front].i;j=qu.data[qu.front].j-1;break;}if(mg[i][j]==0){qu.rear++;//将该相邻方块插入到队列中qu.data[qu.rear].i=i;qu.data[qu.rear].j=j;qu.data[qu.rear].pre=qu.front;//指向路径中上一个方块的下标mg[i][j]=-1;//将其赋值为-1，以避免回过来重复搜索}}}returnfalse;//为找到一条路径时返回false}intmain(){if(!mgpath(1,1,8,8))cout该迷宫问题没有解决！endl;return0;}