迷宫.cpp

用vc++实现迷宫求解的算法

#include <iostream.h>
#include <iomanip.h>
#include <stdio.h>
#include <stdlib.h>

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

#define MazeSize 10
typedef int Status;
typedef int MazeType[MazeSize][MazeSize];

typedef struct PosTpye
{
	int x,y;
}PostType;

typedef struct
{
	int ord;
	PostType seat;
	int di;
}SelemType;

typedef struct Stack  ///构造栈
{
	SelemType *base;
	SelemType *top;
	int stacksize;
}Stack;

Status InitStack(Stack &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;
}

bool EmptyStack(Stack S)  //置栈为空
{
	if(S.top==S.base)return true;
	return false;
}

bool FullStack(Stack S)
{
	if(S.top-S.base>=S.stacksize) return true;
	return false;
}
Status push(Stack &S, SelemType e)
{
	if(FullStack(S)){
		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;
}

void pop(Stack &S,SelemType &e)
{
	if(EmptyStack(S)) return;
	e=* --S.top;
}
PostType NextPos(PostType p,int d)
{
	switch(d)
	{
	case 1: p.y+=1;break;
	case 2: p.x+=1;break;
	case 3: p.y-=1;break;
	case 4: p.x-=1;break;
	}
	return p;
}
Status MazePath(MazeType maze,PostType start,PostType end)
{
	Stack S;
	PostType curpos=start;
	SelemType e;
	int curstep=1;
	InitStack(S);
	do
	{
		if(maze[curpos.x][curpos.y]==0)
		{
			e.ord=curstep;
			e.seat=curpos;
			e.di=1;
            maze[curpos.x][curpos.y]=2;
			push(S,e);
			if(curpos.x==end.x && curpos.y==end.y){
				while(!EmptyStack(S))
				{
					pop(S,e);
					cout<<e.seat.x<<"     "<<e.seat.y<<endl;
				}
				return(true);
			}
				
			curpos=NextPos(curpos,1);
			curstep++;
		}
		else
		{
			if(!EmptyStack(S)){
			    pop(S,e);
				while(e.di==4 && !EmptyStack(S)){
					maze[e.seat.x][e.seat.y]=1;
					pop(S,e);
				}//while
				if(e.di<4){
					e.di++;
					push(S,e);
					curpos=NextPos(e.seat ,e.di);
				}//if
			}//if
		}//else
	}while(!EmptyStack(S));
	return false;
}

void main()
{

	MazeType maze={
	//   0,1,2,3,4,5,6,7,8,9
		{1,1,1,1,1,1,1,1,1,1}, //0
		{1,0,0,1,0,0,0,1,0,1}, //1
		{1,0,0,1,0,0,0,1,0,1}, //2
		{1,0,0,0,0,1,1,0,0,1}, //3
		{1,0,1,1,1,0,0,0,0,1}, //4
		{1,0,0,0,1,0,0,0,0,1}, //5
		{1,0,1,0,0,0,1,0,0,1}, //6
		{1,0,1,1,1,0,1,1,0,1}, //7
		{1,1,0,0,0,0,0,0,0,1}, //8
		{1,1,1,1,1,1,1,1,1,1}  //1
	};
	PosTpye  start={1,1},end={8,8};
	MazePath(maze,start,end);	
}