迷宫求解.txt

迷宫求解的算法,可用于数据结构的教学

#include "stdafx.h"
#include "malloc.h"
#include "stdlib.h"
#include "windows.h"

#define STACK_INIT_SIZE  100
#define STACKINCREMENT   10
#define OVERFLOW         -2
#define OK               1
#define ERROR            0
#define M_X  10
#define M_Y  10

typedef struct{
	int x;
	int y;
}PosType;
typedef struct{
	int     ord;
	PosType seat;
	int     di;
}SElemType;
typedef struct {
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

char maze[M_X][M_Y]={
{'#','#','#','#','#','#','#','#','#','#'},
{'#',' ',' ','#',' ',' ',' ','#',' ','#'},
{'#',' ',' ','#',' ',' ',' ','#',' ','#'},
{'#',' ',' ',' ',' ','#','#',' ',' ','#'},
{'#',' ','#','#','#',' ',' ',' ',' ','#'},
{'#',' ',' ',' ','#',' ',' ',' ',' ','#'},
{'#',' ','#',' ',' ',' ','#',' ',' ','#'},
{'#',' ','#','#','#',' ','#','#',' ','#'},
{'#','#',' ',' ',' ',' ',' ',' ',' ','#'},
{'#','#','#','#','#','#','#','#','#','#'}};


int InitStack(SqStack &S)
{
	S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S.base)
		exit(OVERFLOW);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}
int GetTop(SqStack S,SElemType &e)
{
	if(S.top==S.base)
		return ERROR;
	e=*(S.top-1);
	return OK;
}
bool StackEmpty(SqStack S)
{
	if(S.base==S.top)
		return true;
	else
		return false;
}
int Push(SqStack &S,SElemType e)
{
	if(S.top-S.base >= S.stacksize)
	{
		printf("栈满\n");
		S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
		if(!S.base)
			exit(OVERFLOW);
		S.top=S.base+S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return OK;
}
int Pop(SqStack &S,SElemType &e)
{
	if(S.top==S.base)
		return ERROR;
	e=*--S.top;
	return OK;
}


bool Pass(PosType seat)
{
	if(maze[seat.x][seat.y]==' ')
		return true;
	else
		return false;
}
void FootPrint(PosType seat)
{
	maze[seat.x][seat.y]='*';
}

void MarkPrint(PosType seat)
{
	maze[seat.x][seat.y]='!';
}
PosType NextPos(PosType seat,int i)
{
	switch(i)
	{
	   case 1:
		   seat.y++;
		   return seat;
	   case 2:
		   seat.x++;
		   return seat;
	   case 3:
		   seat.y--;
		   return seat;
	   case 4:
		   seat.x--;
		   return seat;
	}
}


bool MazePath()
{
    PosType start,end,curpos;
	SqStack S;
	int curstep;
	SElemType e;

	start.x=1;
	start.y=1;
	end.x=M_X-2;
	end.y=M_Y-2;
	InitStack(S);
	curpos=start;
	curstep=1;
    do
	{
		if(Pass(curpos))
		{
			FootPrint(curpos);
			e.ord=curstep;
			e.seat=curpos;
			e.di=1;
			Push(S,e);
			if(curpos.x==end.x && curpos.y==end.y)
				return true;
			curpos=NextPos(curpos,1);
			curstep++;
		}
		else
		{
			if(!StackEmpty(S))
			{
				Pop(S,e);
				while(e.di==4 && !StackEmpty(S))
				{
					MarkPrint(e.seat);
					Pop(S,e);
				}
				if(e.di<4)
				{
					e.di++;
					Push(S,e);
					curpos=NextPos(e.seat,e.di);
				}
			}
		}
	}while(!StackEmpty(S));
	return false;
}


void SetColor(unsigned short ForeColor,unsigned short BackGroundColor) 
  //给参数默认值，使它可以接受0/1/2个参数 
{ 
   HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);    //本例以输出为例
   SetConsoleTextAttribute(hCon,ForeColor|BackGroundColor); 
 }



void disp()
{
   int i,j;
   for(i=0;i<=M_X-1;i++)
   {
	  for(j=0;j<=M_Y-1;j++)
	  {
	     switch(maze[i][j])
		 {
		    case '#':
               SetColor(15,0);
			   break;
			case '*':
               SetColor(10,0);
			   break;
			case '!':
               SetColor(12,0);
		 }
		 printf("%c",maze[i][j]);
	  }
	  printf("\n");
   }
   printf("\n");
}


void main()
{
	disp();
	MazePath();
    //SetColor(3,0);
	disp();

}