数据结构-迷宫求解算法
- 格式：doc
- 大小：60.50 KB
- 文档页数：6
#include <stdio.h>
#include <stdlib.h>
#define overflow -1
#define ok 1
#define error 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
typedef struct
{
int x;
int y;
}PosType;//位置类型
typedef struct
{
int row,col;
int a[50][50];
}MazeType;//迷宫类型
typedef struct
{
int ord;//通道块在路径上的序号
PosType seat;//通道块在迷宫中的“坐标位置”
int di;//从此通道块走向下一个通道块的方向
}SElemType;//栈的元素类型
typedef struct
{
SElemType *base;
SElemType *top;
int Stacksize;
}SqStack;//栈结构
Status InitStack(SqStack &S)//初始化栈
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) exit (overflow);
S.top=S.base;
S.Stacksize=STACK_INIT_SIZE;
return ok;
}
Status Push(SqStack &S,SElemType e)//入栈
{
if(S.top-S.base>=S.Stacksize)
{
S.base=(SElemType
*)realloc(S.base,(S.Stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit (overflow);
S.top=S.base+S.Stacksize;
S.Stacksize+=STACKINCREMENT;
}
*S.top++=e;
return ok;
}
Status Pop(SqStack &S,SElemType &e)//出栈
{
if(S.top==S.base) return error;
e=*--S.top;
return ok;
}
bool StackEmpty(SqStack S)//判断栈是否为空
{
if(S.top==S.base)
return ok;
else return error;
}
Status InitMaze(MazeType &maze)//初始化迷宫
{
int i,j;
for( j=0;j<maze.col+2;j++)
maze.a[0][j]=1;
for( i=1;i<maze.row+1;i++)
{
maze.a[i][0]=1;
maze.a[i][maze.col+1]=1;
for(int j=1;j<maze.col+1;j++)
scanf("%d",&maze.a[i][j]);
}
for(j=0;j<maze.col+2;j++)
maze.a[maze.row+1][j]=1;
return ok;
}//为了避免检查边界，把迷宫的外围都设成障碍，迷宫的内核是row行，col列的数组
bool Pass(MazeType maze,PosType curpos)//判断是否可以通过
{
return maze.a[curpos.x][curpos.y]==0;
}
Status FootPrint(MazeType &maze,PosType curpos)//留下足迹
{
maze.a[curpos.x][curpos.y]=2;
return ok;
}
SElemType CreatElem(int step,PosType pos,int di)//创造一个SElemType型的数据
{
SElemType e;
e.ord=step;
e.seat=pos;
e.di=di;
return e;
}
bool IsEnd(PosType pos1,PosType pos2)//判断是否结束
{
return pos1.x==pos2.x&&pos1.y==pos2.y;
}
PosType NextPos(PosType curpos,int di)//向下一步搜索
{
PosType pos=curpos;
switch(di)
{
case 1:pos.x++;break;//向东
case 2:pos.y++;break;//向南
case 3:pos.x--;break;//向西
case 4:pos.y--;break;//向北
}
return pos;
}
Status MarkPrint(MazeType &maze,PosType curpos)//在死路处留下印迹
{
maze.a[curpos.x][curpos.y]='*';
return ok;
}
Status MazePath(MazeType &maze,PosType start,PosType end)//寻找路径
{
//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底到栈顶），
//并返回ture；否则返回false
SqStack S;
SElemType e;
InitStack(S);
PosType curpos=start;//设定当前位置为入口位置
int curstep=1;//探索第一步
do{
if(Pass(maze,curpos))
{
FootPrint(maze,curpos);//留下足迹
e=CreatElem(curstep,curpos,1);
Push(S,e);//加入路径
if(IsEnd(curpos,end))
return ok;//达到终点
curpos=NextPos(curpos,1);//下一步是当期位置的东邻
curstep++;//探索下一步
}
else//当前位置不能通过
{
if(!StackEmpty(S))
{
Pop(S,e);
while(e.di==4&&!StackEmpty(S))
{
MarkPrint(maze,e.seat);//留下不能通过的标记，并退一步
Pop(S,e);
}
if(e.di<4)
{
e.di++;//换下一个方向
Push(S,e);
curpos=NextPos(e.seat,e.di);//设定当前位置是新方向上的相邻块
}
}
}
}while(!StackEmpty(S));
return error;
}
Status PrintMaze(MazeType maze)//输出迷宫
{
int i,j;
for(i=0;i<maze.row+2;i++)
{
for(j=0;j<maze.col+2;j++)
printf("%d ",maze.a[i][j]);
printf("\n");
}
return ok;
}
void main()
{
MazeType maze;
printf("请输入迷宫的行数row和列数col：");
scanf("%d %d",&maze.row,&maze.col);
printf("请输入迷宫数据，0表示通道，1表示障碍：\n");
InitMaze(maze);
PosType start,end;
start.x=1;start.y=1;
end.x=maze.row;end.y=maze.col;
if(MazePath(maze,start,end))
{
printf("迷宫走法（2代表走法，*代表不通）\n");
PrintMaze(maze);
}
else
printf("没有找到通路!\n"); }。
