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

文档介绍：经典广度优先搜索算法,用parentx,parenty存储上一步的位置,规范化使用队列和栈。
迷宫暂定为8*6,动态生成,四周为一圈障碍,出口坐标为(8,6)。
坐标的定义类似图形编程的屏幕坐标,横向为x分量,垂直为y分量,左上角为原点。
可以向8个方向试探。
源代码(TC下编译运行通过):
#include <>
#include <>
#define Status int
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
#define ROW 8            /*行列可自定*/
#define COLUM 10      /*行列可自定*/
#define OUT 8
#define STEPPED 2
#define MAXQSIZE 100
int maze[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}};/*此处只是给一个初始化的例子,可以删去,后面的代码可以动态生成迷宫*/
void CreateRandomMaze()/*随机生成迷宫(可能产生走不通的迷宫)*/
{
int i,j;
srand((int)time());/*设置随机数种子,产生真随机数*/
for(i=0;
i<ROW;i++)
{
for(j=0;j<COLUM;j++)
{
maze[i][j]=rand()%2;/*产生0~1的随机数*/
}
}
for(i=0;i<COLUM;i++)
{
maze[0][i]=1;
maze[ROW-1][i]=1;
}
for(i=0;i<ROW;i++)
{
maze[i][0]=1;
maze[i][COLUM-1]=1;
}
maze[1][1]=0;
maze[ROW-2][COLUM-2]=OUT;/*设置出口*/
}
void printMaze()/*打印迷宫*/
{
int i,j;
/*clrscr();*//*这个是turbo C的清屏函数,可以替代或忽略*/
for(i=0;i<ROW;i++)
{
for(j=0;j<COLUM;j++)
{
printf(" %d",maze[i][j]);
}
printf("\n");
}
/*delay(1000);*/
}
/*********************队列(非循环顺序队列)************************/
typedef struct
{
int x,y;
int parentx,parenty;       /*记录上一个节点即路径中前驱节点,方便最后输出*/
}QNode,*Qu