#include "stdlib.h"
#include "stdio.h"
#include "time.h"
#define STACK_INIT_SIZE 10
typedef struct
{
int x; //当前位置的横坐标
int y; //当前位置的纵坐标
char type; //当前位置的属性:墙壁或通道(0/1)
bool isfoot; //判断当位置是否已走过, true代表已走过
}Position; //当前位置信息
typedef struct
{
int order; //脚步在地图上的序号
Position seat; //行走的当前位置
int aspect; //下一步的方向
}Block; //脚步
typedef struct
{
int width; //地图的长度
int height; //地图的宽度
Position* site; //地图内的各个位置
}Maze; //地图
typedef struct
{
Block* base;
Block* top;
int lenght;
int stacksize;
}Stack;
bool InitStack(Stack &S)
{
S.base=(Block*)malloc(STACK_INIT_SIZE*sizeof(Block));
if(!S.base) return 0;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
S.lenght=0;
return 1;
}
bool Push(Stack &S,Block data)
{
if(S.lenght>=S.stacksize)
{
S.base=(Block*)realloc(S.base,(STACK_INIT_SIZE+S.stacksize)*sizeof(Block));
if(!S.base) return 0;
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INIT_SIZE;
}
*S.top=data;
S.top++;
S.lenght++;
return 1;
}
bool Pop(Stack &S,Block &data)
{
if(S.top==S.base) return 0;
S.top--;
data=*S.top;
S.lenght--;
return 1;
}
void DestroyStack(Stack &S)
{
free(S.base);
}
void ClearStack(Stack &S)
{
DestroyStack(S);
InitStack(S);
}
Maze* GreatMaze(int width,int height) //创建地图
{
Maze* maze=(Maze*)malloc(sizeof(Maze)); //为地图分配存放空间
maze->width=width;
maze->height=height;
maze->site=(Position*)malloc(width*height*sizeof(Position)); //为地图坐标分配空间
srand((unsigned)time(NULL)); //产生随机数
int i,k,j=0;
if(width>0&&height>0)
{
for(i=0;i<maze->width;i++)
for(k=0;j<maze->height*(i+1);j++,k++)
{
maze->site[j].x=k;
maze->site[j].y=i;
int n=rand()%9+1;
if(n>5)
maze->site[j].type='0'; //设置墙壁
else
maze->site[j].type='1'; //设置通道
}
}
return maze; //返回定义好的地图
}
void PrintMaze(Maze* maze) //打印地图
{
int i,j=0;
printf("\t");
for(i=0;iwidth;i++)
printf("%d ",i); //打印横坐标
printf("\n");
printf("\n");
for(i=0;iheight;i++)
{
printf("%d\t",i); //打印纵坐标
for(j;jwidth*(i+1);j++)
if(maze->site[j].type=='0')
printf("■"); //打印墙壁
else
printf("□"); //打印通道
printf("\n");
}
}
bool PositionComparison(Position maze,Position pos) //判断当前位置是否合法
{
if(maze.x==pos.x && maze.y==pos.y)
return 1;
else
return 0;
}
bool Pass(Maze* maze,Position curpos)
{
Position *pos;
pos=maze->site;
for(int i=0;iheight*maze->width;i++)
{
if(PositionComparison(*pos,curpos)) //判断当前位置是否合法
if(pos->type=='0'|| maze->site[i].isfoot==true) //判断当前位置是否可以前进或者是否走过
return 0;
else
return 1;
pos++;
}
return 0;
}
void FootSet(Maze* maze,Position site) //留下足迹
{
for(int i=0;iheight*maze->width;i++)
{
if(PositionComparison(maze->site[i],site))
{
maze->site[i].isfoot=true; //留下已走过的足迹
}
}
}
Position NextPos(Position &cur,int aspect)
{
switch(aspect)
{
case 1:cur.y+=1;break; //向下
case 2:cur.x+=1;break; //向右
case 3:cur.y-=1;break; //向上
case 4:cur.x-=1;break; //向左
}
return cur;
}
bool MazePath(Maze* maze,Position start,Position end,Stack &S)
{
int curstep;
Position curpos; //探索的位置
Block path; //脚步
InitStack(S);
curpos.x=start.x;
curpos.y=start.y; //入口
curstep=1; //探索第一步
do
{
if(Pass(maze,curpos)) //当前位置是否可以通过
{
FootSet(maze,curpos); //留下足迹
path.order=curstep; //当前走过的总步数
path.seat=curpos; //踏下脚步
path.aspect=1;
Push(S,path); //保存脚步
if(PositionComparison(curpos,end)) //判断是否是重点
return 1;
curpos=NextPos(curpos,1); //继续向下一个方向探索
curstep++; //探索的步数增加一
}
else
{
if(S.lenght!=0)
{
Pop(S,path); //退到上一步
while(path.aspect==4 && S.lenght!=0) //如果当前位置无法再前行,再退回一步
Pop(S,path);
if(path.aspect<4) //如果当前位置可再继续探索
{
path.aspect++; //转变探索方向
Push(S,path); //保存当前位置(只更新了探索方向)
curpos=NextPos(path.seat,path.aspect); //继续探索下一个方向
}
}
}
}while(S.lenght!=0);
return 0;
}
int main(int argc)
{
Position start,end;
Block blk;
Stack S;
int width,height;
printf("输入迷宫比例X*Y\n");
printf("输入X:");
scanf("%d",&width);
printf("输入Y:");
scanf("%d",&height);
Maze* maze=GreatMaze(width,height);
PrintMaze(maze);
printf("\n");
printf("请输入入口坐标X:");
scanf(" %d",&start.x);
printf("请输入入口坐标Y:");
scanf(" %d",&start.y);
printf("请输入出口坐标X:");
scanf(" %d",&end.x);
printf("请输入出口坐标Y:");
scanf(" %d",&end.y);
MazePath(maze,start,end,S);
printf("走完所需路径长度为:%d",S.lenght);
printf("\n");
Stack Sa;
InitStack(Sa);
while(S.lenght!=0)
{
Pop(S,blk);
Push(Sa,blk);
}
while(Sa.lenght!=0)
{
Pop(Sa,blk);
if(Sa.lenght!=0)
printf("[%d,%d]->",blk.seat.x,blk.seat.y); //打印足迹
else
printf("[%d,%d]",blk.seat.x,blk.seat.y); //打印最后一步
}
}
求帮忙注释,最好能指导下哪里用到了什么