迷宫问题.c

数据结构实验实习题中的迷求解问题的源程序。希望对大家有用！

#include<stdio.h>
#include<malloc.h>
#define len sizeof(SNodeType)
#define ERROR 0
#define OK 1
typedef struct ElemType{
	int x;
	int y;
	int di;
}ElemType;
typedef struct SNodeType{
	ElemType data;
 	struct SNodeType *next;
}SNodeType,*SLinkType;
typedef struct{
	SLinkType top;
	SLinkType base;
	int size;
}Stack;
int Initstack(Stack *S)
{
	S->base=(SLinkType)malloc(len);
	if(!S->base) return ERROR;
	S->top=S->base;
	S->base->next=NULL;
	return OK;
}
int Push(Stack *S,ElemType e)
{
	SLinkType p;
	p=(SLinkType)malloc(len);
	if(!p) return ERROR;
	p->next=S->top;
	S->top->data=e;
	S->top=p;
	return OK;
}
int Pop(Stack *S,ElemType *e)
{
	if(S->top==S->base) return ERROR;
    S->top=S->top->next;
	*e=S->top->data;
	return OK;
}
int StackEmpty(Stack S)
{
	if(S.top==S.base) return OK;
	else return ERROR;
}
void Print(Stack *S)
{
	SLinkType p;
	p=S->top;
	while(p!=S->base)
	{
		p=p->next;
		printf("(%d,%d,%d)  ",p->data.x,p->data.y,p->data.di);
	}
}
void NextPos(ElemType *curpos)
{
	if(curpos->di==1) curpos->y++;
	else if(curpos->di==2) curpos->x++;
	else if(curpos->di==3) curpos->y--;
	else curpos->y--;
	curpos->di=1;
}
int main()
{
	int a[10][11]=
	{
		1,1,1,1,1,1,1,1,1,1,1,
		1,0,0,0,0,0,0,0,1,1,1,
		1,0,0,0,1,0,1,1,1,1,1,
		1,1,1,0,1,0,0,1,0,0,1,
		1,0,0,0,1,1,0,1,0,0,1,
		1,0,0,1,0,1,0,1,0,0,1,
		1,0,0,0,0,0,1,0,1,0,1,
		1,1,1,0,1,0,0,0,0,0,1,
		1,0,0,1,0,0,1,1,1,0,1,
		1,1,1,1,1,1,1,1,1,1,1
	};
    int i,j;
	Stack S,T;
    ElemType start={1,1,1},e,curpos,end={8,9,1};
	curpos=start;
	Initstack(&S);
	Initstack(&T);
	do
	{
		i=curpos.x;
		j=curpos.y;
		if(!a[i][j])
		{
			e=curpos;
			Push(&S,e);
			if((curpos.x==end.x)&&(curpos.y==end.y)) 
			{
               printf("你已经成功的走出了迷宫,以下是迷宫的路径!\n");
			   while(S.top!=S.base) 
			   {
				   Pop(&S,&e);
				   Push(&T,e);
			   }
               Print(&T);
			   printf("\n");
			   for(i=0;i<=9;i++)
			   {
			   for(j=0;j<=10;j++)
				   printf("%2d",a[i][j]);
			   printf("\n");
			}
			   return OK;
			}
			a[i][j]=3;
			NextPos(&curpos);
		}
		else{
			if(!StackEmpty(S))
			{
				Pop(&S,&e);
				while(e.di==4&&!StackEmpty(S))
				{
					a[e.x][e.y]=2;
					Pop(&S,&e);
				}
				if(e.di<4)
				{
					e.di++;
					curpos=e;
					Push(&S,e);
					NextPos(&curpos);
				}
			}
		}
	}while(!StackEmpty(S));
	return ERROR;
}