maze.cpp

以一个mXn的长方阵表示迷宫

#include<iostream>
using namespace std;


typedef struct StackNode
{
	int x,y;
	int dir;
	struct StackNode *next;	
}StackNode;

typedef struct LStack
{
	StackNode *base,*top;
}LStack;

void InitStack (LStack *S);
int Push(LStack *,StackNode *);
int Pop(LStack *,StackNode *);
bool StackEmpty(LStack *S);
void reverse_stack(LStack *S);
int nextstep(StackNode *e);
void outputstack(LStack *S);
void ClearStack(LStack *S);	


void InitStack (LStack *S)
{
	S->top=new StackNode;
	if(!S->top)
	{ 
		cout<<"overflow"<<endl;
		exit (1);
	}

	S->base=S->top;
	S->base->next=NULL;
}




int Push(LStack *S,StackNode *e)
{
	StackNode *p;
	p=S->top;
	S->top=new StackNode;
	if(!S->top)
	{
		cout<<"overflow"<<endl;
		exit (1);
	}
	S->top->next=p;
	S->top->x=e->x;
	S->top->y=e->y;
	S->top->dir=e->dir;
	return 0;
}


int Pop(LStack *S,StackNode *e)
{
	StackNode *p;
	if(!StackEmpty(S))
	{
		p=S->top ;
		e->x=S->top->x;
		e->y=S->top->y;
		e->dir=S->top->dir;
		S->top=S->top->next;
		delete p;
	}
	else
	{
		cout<<"error"<<endl;
		exit(1);
	}	
	return 0;
}

bool StackEmpty(LStack *S)
{
	if(S->base==S->top)
		return true;
	else 
		return false;
}


int nextstep(StackNode *e)
{
	switch(e->dir)
	{
		case 1:	
			e->y++;			
			break;
		case 2:
			e->x++;
			break;
		case 3:
			e->y--;
			break;
		case 4:
			e->x--;
			break;
		default:
			break;
	}
	return 0;
}
void reverse_stack(LStack *S)
{
	StackNode *p,*q;
	p=S->top;
	while(p->next!=S->base)
		p=p->next;
	p->next=NULL;
	S->base->next=S->top;
	p=S->base->next;
	S->base->next=NULL;
	while(p)
	{
		q=p->next;
		p->next=S->base->next;
		S->base->next=p;
		p=q;
	}
}
void outputstack(LStack *S)
{
	StackNode *p;
	p=S->base->next;	
	while(p)
	{
		cout<<"("<<p->x<<","<<p->y<<","<<p->dir<<")"<<endl;
		p=p->next;
	}		
} 
void ClearStack(LStack *S)
{
	StackNode *p,*q;
	p=S->base;
	while(p)
	{
		q=p->next;
		delete p;
		p=q;
	}
}

  
int main()
{
	int m,n,i,j;
	cout<<"输入m,n:"<<endl;
	cin>>m>>n;
	cout<<endl;
	int **c=new int*[m+2];
	for(i=0;i<m+2;i++)
			c[i]=new int[n+2];
	cout<<"输入迷宫:"<<endl;
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			cin>>c[i][j];
		}
	}

	for(i=0;i<m+2;i++)
	{
		c[i][0]=c[i][n+1]=1;
	}
	for(j=1;j<=n;j++)
	{
		c[0][j]=c[m+1][j]=1;
	}
	
	StackNode *e;
	LStack *S;
	e=new StackNode;
	S=new LStack;
	StackNode start,end;
	cout<<"输入起始和结尾:"<<endl;
	cin>>start.x>>start.y>>end.x>>end.y;
	cout<<endl;
	
	InitStack (S);
	e->x=start.x;
	e->y=start.y;
	e->dir=1;
	e->next=NULL;
	do
	{
		if(c[e->x][e->y]==0)
		{
		    c[e->x][e->y]=2;
			e->dir=1;
			Push(S,e);			
			nextstep(e);			
		}
		else
		{
			if(!StackEmpty(S))
			{
				Pop(S,e);				
				while(e->dir ==4&&!StackEmpty(S))
				{
					c[e->x][e->y]=3;
					Pop(S,e);													
				}
				
				if(e->dir<4)
				{
					e->dir++;
					Push(S,e);
					nextstep(e);
				}
			
			}
		}
	}while ((e->x!=end.x||e->y!=end.y)&&!StackEmpty(S));
	Push(S,e);
	c[e->x][e->y]=2;
	reverse_stack(S);
	if(S->top->x==end.x&&S->top->y==end.y)
	{
		cout<<"输出栈:"<<endl;
		outputstack(S);
		cout<<"输出迷宫："<<endl;	
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			{
				cout<<c[i][j]<<' ';
			}
			cout<<endl;
		}
	}
	else
	{
		cout<<"找不到路径"<<endl;
	}
	for(i=0;i<m+2;i++)
		delete []c[i];
	ClearStack(S);
	return 0;
}

/*0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0*/