maze.c

典型的迷宫算法

//计算机与信息技术学院  生物0501
//尚倩  第四次作业  迷宫
//05282016
#include<stdio.h>
#include<malloc.h>
#define STACK_INIT_SIZE 100//存储空间初始分配量
#define STACKINCREMENT 10//存储空间分配增量
#define TURE 1
#define FALSE 0
#define OK 1
#define OVERFLOW -2
#define error 0
typedef struct//坐标位置类型
{
	int x;
	int y;
}PosType;
typedef int MazeType[10][10];
typedef struct//栈的元素类型
{
	int ord;
	PosType seat;
	int di;
}SElemType;

typedef struct
{
	SElemType *base;//在栈构造之前和销毁之后， base得值为NULL
	SElemType *top;//栈顶指针
	int stacksize;//当前已分配的存储空间，以元素为单位
}SqStack;
//1 构建一个空栈
int InitStack(SqStack *s)
{
	(*s).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!(*s).base) return OVERFLOW;//存储分配失败
	(*s).top=(*s).base;
	(*s).stacksize=STACK_INIT_SIZE;
	return OK;//成功返回OK
}
//2 销毁栈
int DestoryStack(SqStack *s)
{
	if((!(*s).base)) return OVERFLOW;
	free((*s).base);
	return OK;
}
//3把栈置为空栈
int ClearStack(SqStack *s)
{
	if((!(*s).base)) return OVERFLOW;
	(*s).top=(*s).base;
	return OK;
}
//4判断栈是否为空
int StackEmpty(SqStack s)
{
	if(!s.base) return OVERFLOW;
	if(s.top==s.base)
		return TURE;
	else
		return FALSE;
}
//5 求栈的长度
int StackLength(SqStack s)
{
	if((!s.base)) return OVERFLOW;
	return (s.top-s.base);
}
//6取栈顶元素
int GetTop(SqStack s,SElemType *e)//若栈不空，用e返回栈顶元素，并返回OK,否则，返回error
{
	
	if((!s.base)) return OVERFLOW;
	if(s.top==s.base)
		return error;
	*e=*(s.top-1);
	return OK;
}
//7 压栈
int Push(SqStack *s,SElemType e)//插入e为新的栈顶元素
{
	if((!(*s).base)) return OVERFLOW;
	if(((*s).top-(*s).base)>=(*s).stacksize)//栈满，追加存储空间
	{
		(*s).base=(SElemType*)realloc((*s).base,((*s).stacksize+STACKINCREMENT)*sizeof(SElemType));
		if((!(*s).base)) return OVERFLOW;//存储分配失败
		(*s).top=(*s).base+(*s).stacksize;
		(*s).stacksize+=STACKINCREMENT;
	}
	*((*s).top)++=e;	
	return OK;
}
//7 弹出栈顶元素
int Pop(SqStack *s,SElemType *e)//若栈不空，删除S的栈顶元素，并用e返回其值，并返回OK,否则，返回error
{
	if((!(*s).base)) return OVERFLOW;
	if((*s).top==(*s).base)
		return error;
	*e=*--(*s).top;	
	return OK;
}
//8遍历
int StackTraverse(SqStack s,int(*visit)())
{
	int i;
	if((!s.base)) return OVERFLOW;
	for(i=1;i<=s.top-s.base;i++)
	{
		(*visit)("%d",*(s.top-i));
	}
	return OK;
}

//10 输出
int OutPutStack(SqStack s)
{
	SElemType *p;
	if((!s.base)) return OVERFLOW;
	for(p=s.base;p<=s.top;p++)
	{
		printf("栈中的元素为：");
		printf("%c  ",*p);
	}
	return OK;
}
int Pass(PosType a,MazeType maze)
{
	if(maze[a.x][a.y]==1)
		return    TURE;
	else
		return    FALSE;
}
void FootPrint(PosType a,MazeType maze)//走过的元素置0
{
	maze[a.x][a.y]=0;
}
PosType NextPos(PosType a,int n)//取下一个元素
{
	PosType p;
	switch(n)
	{
	case 1:
		{
			p.x=a.x;
			p.y=a.y+1;
			break;
		}
	case 2:
		{
			p.x=a.x-1;
			p.y=a.y;
			break;
		}
	case 3:
		{
			p.x=a.x;
			p.y=a.y-1;
			break;
		}
	default:
		{
			p.x=a.x+1;
			p.y=a.y;
			break;
		}
	}
	return p;
}
int MazePath(MazeType maze,PosType start,PosType end,SqStack *s)
{
	
	PosType curpos;
	int curstep;
	SElemType e;
	InitStack(s);
	curpos=start;
	curstep=1;
	do{
		if(Pass(curpos,maze))
		{
			FootPrint(curpos,maze);
			e.ord=curstep;e.seat=curpos;e.di=1;
			Push(s,e);
			if(curpos.x==end.x&&curpos.x==end.y) return TURE;
			curpos=NextPos(curpos,1);
			curstep++;
		}
		else{
			if(!StackEmpty(*s))
			{
				Pop(s,&e);
				while(e.di==4&&!StackEmpty(*s))
				{
					FootPrint(e.seat,maze);Pop(s,&e);
				}
				if(e.di<4)
				{
					e.di++;
					Push(s,e);
					curpos=NextPos(e.seat,e.di);
					
				}
			}
		}
	
	}while(!StackEmpty(*s));
	return FALSE;
}

void main()
{
	int i,j,k;
	PosType start={1,1};
	PosType end={8,8};
	SqStack s;
	MazeType maze={{0,0,0,0,0,0,0,0,0,0},
					{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,1},
					{0,1,1,1,0,1,1,1,1,1},
					{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}};
	printf("该迷宫为(1为通道，0为墙):\n");
	for(j=0;j<10;j++)
	{	
		for(k=0;k<10;k++)
		printf("%d  ",maze[j][k]);
		printf("\n");
	}
	MazePath(maze,start,end,&s);
	printf("该迷宫走法为：\n");
	printf("入口：第%d行第%d列\n",(*(s.base)).seat.x+1,(*(s.base)).seat.y+1);
	for(i=1;i<StackLength(s)-1;i++)
		printf("第%d步,第%d行第%d列\n",(*(s.base+i-1)).ord,(*(s.base+i)).seat.x+1,(*(s.base+i)).seat.y+1);
	printf("出口：第%d行第%d列\n",(*(s.base+StackLength(s)-1)).seat.x+1,(*(s.base+StackLength(s)-1)).seat.y+1);
}