迷宫算法(经典广度优先搜索算法)

《迷宫算法(经典广度优先搜索算法)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、经典广度优先搜索算法，用parentx,parenty存储上一步的位置，规范化使用队列和栈。迷宫暂定为8*6，动态生成，四周为一圈障碍，出口坐标为（8，6）。坐标的定义类似图形编程的屏幕坐标，横向为x分量，垂直为y分量，左上角为原点。可以向8个方向试探。源代码（TC下编译运行通过）：#include#include#defineStatusint#defineOK1#defineERROR0#defineOVERFLOW-2#defineTRUE1#defineFALSE0#defineROW8           /*行列可自定*/#defin

2、eCOLUM10     /*行列可自定*/#defineOUT8#defineSTEPPED2#defineMAXQSIZE100intmaze[8][10]/*6行8列*/={{1,1,1,1,1,1,1,1,1,1},{1,0,1,1,1,1,0,0,0,1},{1,0,1,0,0,1,1,0,0,1},{1,0,0,0,1,0,1,0,0,1},{1,1,1,0,1,0,1,0,0,1},{1,0,0,0,0,0,0,0,0,1},{1,0,0,0,0,0,0,1,OUT,1},{1,1,1,1,1,1,1,1,1,1}};/*此处只是给一个初始化的例子，可以删去，后面的代码

3、可以动态生成迷宫*/voidCreateRandomMaze()/*随机生成迷宫（可能产生走不通的迷宫）*/{inti,j;srand((int)time());/*设置随机数种子，产生真随机数*/for(i=0;i

4、[ROW-2][COLUM-2]=OUT;/*设置出口*/}voidprintMaze()/*打印迷宫*/{inti,j;/*clrscr();*//*这个是turboC的清屏函数，可以替代或忽略*/for(i=0;i

5、     /*记录上一个节点即路径中前驱节点，方便最后输出*/}QNode,*QueuePtr;typedefQNodeElemType;typedefstructSqQueue{ElemType*base;intfront;intrear;}SqQueue;/*队列结构体*/StatusInitQueue(SqQueue*Q)/*初始化队列*/{Q->base=(ElemType*)malloc(MAXQSIZE*sizeof(ElemType));if(!Q->base){exit(OVERFLOW);}Q->front=Q->rear=0;returnOK;}intQueueL

6、ength(SqQueueQ){returnQ.rear-Q.front;}StatusQueueEmpty(SqQueueQ){if(Q.front==Q.rear){returnTRUE;}returnFALSE;}StatusGetHead(SqQueueQ,ElemType*e){if(Q.front==Q.rear){returnERROR;}*e=Q.base[Q.front];returnOK;   }StatusEnQueue(SqQueue*Q,ElemTypee){if(Q->rear>MAXQSIZE-1)/*队列满*/{returnERROR;}Q->base

7、[Q->rear]=e;(Q->rear)++;returnOK;}StatusDeQueue(SqQueue*Q,ElemType*e){if(Q->front==Q->rear)/*队列空*/{returnERROR;}*e=Q->base[Q->front];(Q->front)++;returnOK;}/*********************栈**********************/typedefstruct{inttop,base,co