mm.cpp

数据结构中常见的迷宫求解问题 使用顺序栈 初学者适用

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INIT_SIZE 100
#define INCREMENT 10
typedef int Status;
typedef struct//迷宫中r行c列的位置
{
	int r;
	int c;
}PostType;
typedef struct
{
	int ord;
	PostType seat;
	int di;
}SElemType;
typedef struct
{
	SElemType *base;
	SElemType *top;
	int stackSize;
}Stack;
Status InitStack(Stack &S)
{
	S.base=(SElemType *)malloc(INIT_SIZE *sizeof(SElemType));
	if(!S.base)
		exit(0);
	S.top=S.base;
	S.stackSize=INIT_SIZE;
	return 1;
}
Status StackEmpty(Stack S)
{
	if(S.top==S.base)
		return 1;
	return 0;
}
Status Push(Stack &S,SElemType e)
{
	if(S.top-S.base>=S.stackSize)
	{
		S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
		if(!S.base)
			exit(0);
		S.top=S.base+S.stackSize;
		S.stackSize+=INCREMENT;
	}
	*S.top++=e;
	return 1;
}
Status Pop(Stack &S,SElemType &e)
{
	if(S.top==S.base)
		return 0;
	e=*--S.top;
	return 1;
}
Status DestroyStack(Stack &S)
{
	free(S.base);
	S.top=S.base;
	return 1;
}
Status FootPrint(char adr[10][10],PostType curpos)
{
	adr[curpos.c][curpos.r]='@';
	return 1;
}
Status Pass(char adr[10][10],PostType &curpos)
{
	if(adr[curpos.r][curpos.c]==' ')
		return 1;
	else
		return 0;
}
PostType NextPos(PostType &curpos,int b)
{
	PostType a;
	a=curpos;
	if(b==1)a.c+=1;
	if(b==2)a.r+=1;
	if(b==3)a.c-=1;
	if(b==4)a.r-=1;
	return (a);
}
Status MarkPrint(char adr[10][10],PostType curpos)
{
	adr[curpos.r][curpos.c]='*';
	return 1;
}
Status MazePath(char adr[10][10],PostType start,PostType end)
{
	Stack S;
	PostType curpos;
	int curstep;
	SElemType e;
	InitStack(S);
	curpos=start;
	curstep=1;
	do
	{
		if(Pass(adr,curpos))
		{
			FootPrint(adr,curpos);
			e.ord=curstep;
			e.seat=curpos;
			e.di=1;
			Push(S,e);
			if(curpos.r==end.r&&curpos.c==end.c)
			{
				DestroyStack(S);
				return 1;
			}
			else
			{
				curpos=NextPos(curpos,1);
				curstep++;
			}
		}
		else
		{
			if(!StackEmpty(S))
			{
				Pop(S,e);
				while(e.di==4&&!StackEmpty(S))
				{
					MarkPrint(adr,e.seat);
					Pop(S,e);
				}
				if(e.di<4)
				{
					e.di++;
					Push(S,e);            
					curpos=NextPos(e.seat,e.di);
				}
			}
		}
	}while(!StackEmpty(S));
	DestroyStack(S);
	return 0;
}
void PrintMaze(char adr[10][10])
{
	int i,j;
	for(i=0;i<10;i++)
	{
		for(j=0;j<10;j++)
			printf("%2c",adr[i][j]);
		printf("\n");
	}
}
void main()
{
	int i,j;
	 char adr[10][10]={
		{'1','1','1','1','1','1','1','1','1','1'},
		{'1',' ',' ','1',' ',' ',' ','1',' ','1'},
		{'1',' ',' ','1',' ',' ',' ','1',' ','1'},
		{'1',' ',' ',' ',' ','1','1',' ',' ','1'},
		{'1',' ','1','1','1',' ',' ',' ',' ','1'},
		{'1',' ',' ',' ','1',' ',' ',' ',' ','1'},
		{'1',' ','1',' ',' ',' ','1',' ',' ','1'},
		{'1',' ','1','1','1',' ','1','1',' ','1'},
		{'1','1',' ',' ',' ',' ',' ',' ',' ','1'},
		{'1','1','1','1','1','1','1','1','1','1'}};
		/*int adr[10][10]={
		{1,0,1,1,1,1,1,1,1,1},
		{1,0,0,1,0,0,0,1,0,1},
		{1,0,0,1,0,0,0,1,0,1},
		{1,0,0,0,0,1,1,0,0,1},
		{1,0,1,1,1,0,0,0,0,1},
		{1,0,0,0,1,0,0,0,0,1},
		{1,0,1,0,0,0,1,0,0,1},
		{1,0,1,1,1,1,1,1,0,1},
		{1,1,0,0,0,0,0,0,0,1},
		{1,1,1,1,1,1,1,1,0,1}};*/
	PrintMaze(adr);
	PostType start,end;
	start.r=1;start.c=1;
	end.r=8;end.c=8;
	if(!MazePath(adr,start,end))
		printf("\n迷宫没有通路!\n");
	else
	{
		printf("\n结果:\n\n");
		PrintMaze(adr);
	}
	for(i=0;i<10;i++)
		for(j=0;j<10;j++)
		{
			if(adr[i][j]=='%')
				printf("(%d,%d)\n",i,j);
		}
}