迷宫问题
我照这书上写了迷宫问题，但是总是不对，哪位大侠帮忙看下，只说下思路就行了，谢谢#include <stdio.h>
#define InitSize 100
#define Increment 20
#define N 10
typedef struct PosType
{
int row;
int col;
}PosType;
typedef struct
{
int ord;
PosType seat;
int di;
}SElemType;
typedef struct Stack
{
SElemType * top;
SElemType * base;
int size;
}Stack;
typedef struct
{
int a[N][N];
}MazeType;
void StackInit(Stack *S)
{
S->top=S->base=(SElemType *)malloc(InitSize *sizeof(SElemType));
if(!S->top)
exit (1);
S->size=InitSize;
}
SElemType Gettop(Stack S)
{
return *(S.top-1);
}
void Push(Stack *S,SElemType x)
{
if(S->top-S->base>=S->size)
{
S->base=(SElemType *)realloc((S->size+Increment)*sizeof(SElemType));
if(!S->base)
exit (0);
}
*(S->top++)=x;
}
void Pop(Stack *S,SElemType *x)
{
if(S->top-S->base!=0)
*x=*(--S->top);
}
int StackEmpty(Stack S)
{
if(S.top==S.base)
return 1;
else
return 0;
}
int Pass(PosType step,MazeType maze)
{
if(maze.a[step.row][step.col]=1)
return 1;
else
return 0;
}
void FootPrint(PosType step,MazeType *maze)
{
maze->a[step.row][step.col]=5;
}
void MarkPrint(PosType step,MazeType *maze)
{
maze->a[step.row][step.col]=9;
}
PosType NextStep(PosType p,int i)
{
PosType pos;
switch(i)
{
case 1:pos.row=p.row;pos.col=p.col+1;return pos;
case 2:pos.row=p.row+1;pos.col=p.col;return pos;
case 3:pos.row=p.row;pos.col=p.col-1;return pos;
case 4:pos.row=p.row-1;pos.col=p.col;return pos;
}
}
void MazeInit(MazeType *maze)
{
int j,i;
for(j=0;j<N;j++)
{
maze->a[0][j]=maze->a[N-1][j]=0;
maze->a[j][0]=maze->a[j][N-1]=0;
}
for(i=1;i<N-1;i++)
for(j=1;j<N-1;j++)
maze->a[i][j]=1;
}
int MazePath(MazeType *maze,PosType start,PosType end)
{
int curstep=1,i,j;
PosType curpos=start;
Stack st;
SElemType e;
StackInit(&st);
printf("迷宫为:\n");
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
printf("%d",maze->a[i][j]);
printf("\n");
}
do{
if(Pass(curpos,*maze))
{
FootPrint(curpos,maze);
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push(&st,e);
if(curpos.col==end.col&&curpos.row==end.row)
return 1;
else
{
curpos=NextStep(curpos,1);
curstep++;
}
}
else
{
if(!StackEmpty(st))
Pop(&st,&e);
while(e.di==4&&!StackEmpty)
{
MarkPrint(e.seat,maze);
Pop(&st,&e);
}
if(e.di<4)
{
e.di++;
Push(&st,e);
curpos=NextStep(e.seat,e.di);
}
}
}while(!StackEmpty(st));
return 0;
}
int main(void)
{
MazeType m;
int x,y,i,j;
PosType start={1,1},end={8,8};
MazeInit(&m);
printf("输入不可通的位置的坐标x,y（0结束）:");
while(x!=0)
{
scanf("%d",&x);
scanf("%d",&y);
m.a[x][y]=0;
printf("输入不可通的位置的坐标x,y（0结束）:");
}
MazePath(&m,start,end);
printf("\n");
for(i=1;i<N;i++)
{
for(j=1;j<N;j++)
printf("%d",m.a[i][j]);
printf("\n");
}
return 0;
}
