#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 10000
#define STACKINCREMENT 100
#define M 10
#define N 10
int flag=0;
typedef struct//坐标位置
{
int x;
int y;
}PosType;
typedef struct//栈中元素结构体
{
int ord;//序号
PosType seat;//坐标位置
int di;//通道方向(1东2南3西4北)
}SElemType;
typedef struct//栈
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
////////////////////////////////////////栈操作
void initialStack(SqStack *s)
{
s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!s->base) exit(0);
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *s,SElemType e)
{
if(s->top-s->base>=s->stacksize)
{
s->base=(SElemType *)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType));
if(!s->base) exit(0);
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
(*(s->top)).ord=e.ord;
(*(s->top)).seat.x=e.seat.x;
(*(s->top)).seat.y=e.seat.y;
(*(s->top)).di=e.di;
s->top++;
}
void Pop(SqStack *s,SElemType *e)
{
if(s->top==s->base) exit(0);
(s->top)--;
e->ord=(*(s->top)).ord;
e->seat.x=(*(s->top)).seat.x;
e->seat.y=(*(s->top)).seat.y;
e->di=(*(s->top)).di;
}
int StackEmpty(SqStack *s)
{
if(s->top==s->base) return(1);
else return(0);
}
void ClearStack(SqStack *s)
{
s->top=s->base;
s->stacksize=0;
}
//////////////////////////////////////////初始化迷宫
void initialarray(int (*p)[N])
{
int i,j;
int maze[M][N]={1,1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,0,0,1,0,1,0,1,
1,0,0,1,1,0,0,0,0,1,
1,1,1,1,1,0,0,1,0,1,
1,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,1,1,0,0,1,
1,0,1,1,1,0,1,1,0,1,
1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1};/***/
printf("打印迷宫:\n");
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
printf("%d",maze[i][j]);
*(*(p+i)+j)=maze[i][j];/***/
}
printf("\n");
}
}
///////////
void NextPos(PosType *p,int d)//确定下一个位置的坐标
{
switch(d)
{
case 1:p->y++;break;
case 2:p->x++;break;
case 3:p->y--;break;
case 4:p->x--;break;
}
/////////////////////////(1东2南3西4北)改变坐标
}
void MazePath(int (*maze)[N])//核心函数//---int (*maze)[N]
{
int curstep;
int mark[M][N]={0};
SqStack s;
PosType curpos;
SElemType e;//栈中元素结构体 1.序号;2.坐标位置;3.通道方向
initialStack(&s);
curpos.x=1;
curpos.y=1;
curstep=1;
do
{
if((!maze[curpos.x][curpos.y])&&(!mark[curpos.x][curpos.y]))//*******
{
mark[curpos.x][curpos.y]=1;
e.ord=curstep;//**e=(curstep,curpos,1)
e.seat.x=curpos.x;
e.seat.y=curpos.y;
e.di=1;//***
Push(&s,e);
if((curpos.x==M-2)&&(curpos.y==N-2))
{
flag=1;
printf("走出迷宫的一条坐标路径为:\n[终点]");
while(!StackEmpty(&s))
{
Pop(&s,&e);
printf("<--(%d,%d)",e.seat.x,e.seat.y);
}
printf("<--[起点]");
printf("\n");
ClearStack(&s);
}
NextPos(&curpos,1);//curpos=NextPos(curpos,1)
curstep++;
}
else
{
if(!StackEmpty(&s))
Pop(&s,&e);
while(e.di==4&&!StackEmpty(&s))
{
mark[e.seat.x][e.seat.y]=1;
Pop(&s,&e);
}
if(e.di<4)
{
e.di++;
Push(&s,e);
curpos.x=e.seat.x;//**curpos=NextPos(e.seat,e,di)
curpos.y=e.seat.y;
NextPos(&curpos,e.di);///**
}
}
}while(!StackEmpty(&s));
}
void main()
{
int array[M][N];
initialarray(array);
MazePath(array);
if(flag==0)
printf("该迷宫不能走出去!\n");
}
