#include<stdio.h>
#include<stdlib.h>
#define N 10
#define INIT_STACK_SIZE 20
#define STACKINCREMENT 10
typedef struct{
int *base;
int *top;
int stacksize;
}SqStack;

int maze[N][N]={0,0,0,0,0,0,0,0,0,0, //0代表障碍，1代表路径
0,1,1,0,1,1,1,0,1,0,
0,1,1,0,1,1,1,0,1,0,
0,1,1,1,1,0,0,1,1,0,
0,1,0,0,0,1,1,1,1,0,
0,1,1,1,0,1,1,1,1,0,
0,1,0,1,1,1,0,1,1,0,
0,1,0,0,0,1,0,0,1,0,
0,0,1,1,1,1,1,1,1,0,
0,0,0,0,0,0,0,0,0,0};

SqStack InitStack(SqStack S);
SqStack FoundPath(SqStack S,int maze[N][N]);
SqStack Push(SqStack S,int path);
SqStack Pop(SqStack S,int *path);
int EmptyStack(SqStack S);

int main(void)
{
SqStack S;
int path;

S=InitStack(S);
S=FoundPath(S,maze);
while(!EmptyStack(S))
{
S=Pop(S,&path);
printf("%d->",path);
}
printf("\n");
free(S.base);

return 0;
}

SqStack InitStack(SqStack S)
{
if((S.base=(int *)malloc(INIT_STACK_SIZE * sizeof(int)))==NULL)
{
exit(1);
}
S.top=S.base;
S.stacksize=INIT_STACK_SIZE;

return S;
}

SqStack FoundPath(SqStack S,int maze[N][N])
{
int i,j,path;

i=1; j=1; maze[8][8]=88;
while(maze[i][j]!=maze[8][8])
{
if(maze[i][j]==1)
{
path=10*i+j; //把当前可通路径压入栈
S=Push(S,path);
maze[i][j]=0;
j++; //继续向东走
}
else if(maze[i][j]==0) //当前位置不可通，向南走
{
if(!EmptyStack(S)) //当前栈不空
path=*(S.top-1);
i=path/10;
j=path%10;
i++; //向南走
if(maze[i][j]==1)
{
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else if(maze[i][j]==0) //向南走不通，向西走
{
if(!EmptyStack(S))
path=*(S.top-1);
i=path/10;
j=path%10;
j--;
if(maze[i][j]==1) //向西走通
{
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else if(maze[i][j]==0) //向西走不通
{
if(!EmptyStack(S))
path=*(S.top-1);
i=path/10;
j=path%10;
i--;
if(maze[i][j]==1) //向北走通
{
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else //都走不通时
{
if(!EmptyStack(S))
S=Pop(S,&path);
i=path/10;
j=path%10;
}
}//else
}//else
}//else
}//while
if(maze[i][j]==maze[8][8])
{
path=10*i+j;
S=Push(S,path);
}

return S;
}

int EmptyStack(SqStack S)
{
int flag=0;

if(S.top==S.base)
flag=1;

return flag;
}

SqStack Push(SqStack S,int path)
{
*(S.top++)=path;
if(S.top-S.base >= S.stacksize)
{
if((S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(int)))==NULL)
{
exit(1);
}
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}

return S;
}

SqStack Pop(SqStack S,int *path)
{
if(!EmptyStack(S))
*path=*(--S.top);

return S;
}

请诸位指教