#include
#include
typedef struct
{
int x,y;
}p;
typedef struct
{
int ord;
p seat;
int di;
}node;
typedef struct
{ node *base,*top;
int stacksize;
}sqstack;
int initstack(sqstack &s) //创建栈
{
s.base=(node )malloc(100*sizeof(node));
if(!s.base) exit(-1);
s.top=s.base;
s.stacksize=100;
return 1;
}
void push(sqstack &s,node e) //压栈
{
if(s.top-s.base>=s.stacksize)
s.base=(node *)realloc(s.base,(s.stacksize+100)*sizeof(node));
if(!s.base) exit(-1);
*s.top++=e;
}
void pop(sqstack &s,node &e) //出栈
{
if(s.top==s.base) return;
e=--s.top;
}
node gettop(sqstack s,node &e) //得到栈顶元素
{ e=*(s.top-1);
return e;
}
int stackempty(sqstack s) //判断栈是否为空
{return s.top==s.base;}
int pass(int **maze,p pos) // 判断是否能够通过
{
if(maze[pos.x][pos.y]==0)
return 1;
return 0;
}
void footprint(int **maze,p pos)
{
maze[pos.x ][pos.y ]=8;
}
void markprint(int maze,p pos)
{
maze[pos.x ][pos.y ]=4;
}
void printffrombase(sqstack &s,int **maze,int row,int line) //从栈底输出路径
{
int i,j;
node *l;
l=s.base;
printf("\n迷宫显示的路径:\n");
for(i=0;i
{
for(j=0;j
{
if(maze[i][j]==1)
printf("■ ");
if(maze[i][j]==0)
printf("□ ");
if((maze[i][j]!=1)&&(maze[i][j]!=0))
printf(" %d ",maze[i][j]);
}
printf("\n");
}
printf("走出迷宫的路径:\n");
while(l!=s.top) //输出路径
{
printf("",l->seat.x,l->seat.y);
printf("->");
l++;
}
printf("成功走出\n");
printf("\n*在迷宫中每一位置按右、上、左、下判断能否通过***\n");
printf("\n***迷宫中8表示走过的路径,4表示的是走过的错误路径***\n");
}
p nextpos(p curpos,int di)
{
/* if(di==1)
{
curpos.y=curpos.y+1; //向右
}
if(di==2)
{
curpos.x=curpos.x-1; //向上
}
if(di==3)
{
curpos.y=curpos.y-1; //向左
}
if(di==4)
{
curpos.x=curpos.x+1; //向下
}*/
switch(di){
case 1: curpos.y=curpos.y+1;break;
case 2: curpos.x=curpos.x-1;break;
case 3: curpos.y=curpos.y-1;break;
case 4: curpos.x=curpos.x+1;break;
}
return curpos;
}
int main() //构建和初始化迷宫
{
int maze=NULL;
int i,row,line;
int j,choice;
printf("请输入序号选择产生迷宫的类型【1.随机产生 2.规定数组产生】\n");
scanf("%d",&choice);
printf("自动生成迷宫四周墙壁\n");
printf("请输入迷宫的行和列(x y):\n");
scanf("%d %d",&row,&line); //输入迷宫的行和列
printf("*实心方块为墙壁,空心方块为路***\n");
maze=(int **)malloc((row+2)*sizeof(int *));
for(i=0;i<row+2;i++)
maze[i]=(int *)malloc((line+2)*sizeof(int));
if(choice==1)
{
for(i=1;i<=row;i++)
for(j=1;j<=line;j++)
maze[i][j]=rand()%2;
printf("********************************\n");
printf("********自动生成迷宫如下********\n");
printf("********************************\n");
for(i=0;i<line+2;i++) //
maze[0][i]=1;
for(i=0;i<line+2;i++) //
maze[row+1][i]=1;
for(i=0;i<row+2;i++) //
maze[i][0]=1;
for(i=0;i<row+2;i++) // 生成四周墙壁
maze[i][line+1]=1;
printf(" ");
for(j=0;j<line+2;j++) // 迷宫每一列序号
printf(" %d ",j);
printf("\n");
for(i=0;i<row+2;i++) //输出迷宫
{
printf("%d ",i); // 迷宫每一行序号
for(j=0;j<line+2;j++)
{
if(maze[i][j]==1)
printf("■ ");
else
printf("□ ");
}
printf("\n");
}
printf("********************************\n");
printf("********************************\n");
}
else
{
printf("请输入迷宫:\n");
int temp;
for (i=1;i<=row;i++)
{
for(int j=1;j<=line;j++)
{
scanf("%d",&temp);
maze[i][j]=temp;
}
}
printf("************************\n");
printf("****规定数组产生迷宫****\n");
printf("************************\n");
for(i=0;i<line+2;i++)
maze[0][i]=1;
for(i=0;i<line+2;i++)
maze[row+1][i]=1;
for(i=0;i<row+2;i++)
maze[i][0]=1;
for(i=0;i<row+2;i++)
maze[i][line+1]=1;
printf(" ");
for(j=0;j<line+2;j++) // 迷宫每一列序号
printf(" %d ",j);
printf("\n");
for(i=0;i<row+2;i++) //输出迷宫
{
printf(" %d ",i);
for(j=0;j<line+2;j++)
{
if(maze[i][j]==1)
printf("■ ");
else
printf("□ ");
}
printf("\n");
}
printf("************************\n");
printf("************************\n");
}
printf("\n");
int a,b,c,d; //curstep=1;
p start,end,curpos;
printf("***迷宫的起点和终点不能为墙壁***\n\n");
printf("请输入起点坐标:\n");
scanf("%d %d",&a,&b);
printf("请输入终点坐标:\n");
scanf("%d %d",&c,&d);
start.x=a,start.y=b;
end.x=c,end.y=d;
sqstack stack;
initstack(stack);
curpos=start;
if(maze[start.x][start.y]==1 ||maze[end.x][end.y]==1)
{
printf("\n***此迷宫无解***\n");
return 1;
}
do
{
if(pass(maze,curpos))
{
footprint(maze,curpos);
node e;
// e.ord=curstep;
e.seat=curpos;
e.di=1;
push(stack,e);
if(curpos.x==end.x&&curpos.y==end.y) //判断是否为终点
{
printffrombase(stack,maze,row,line);
return 0;
}
curpos=nextpos(curpos,1);
// curstep++;
}//if pass
else
{
if(!stackempty(stack))
{
node e;
pop(stack,e);
while(e.di==4 && !stackempty(stack))
{
markprint(maze,e.seat);
pop(stack,e);
}//while
if(e.di<4)
{
e.di++;
push(stack,e);
curpos=nextpos(e.seat,e.di);
}//if
}//if
if(stackempty(stack))
{
printf("\n***此迷宫无解***\n");
return 1;
}
}//else
}while(!stackempty(stack));
return 0;
}