migong.cpp

传统的老鼠走迷宫程序 通过堆栈来实现的 C++ 程序

#include <iostream.h>

int px[8]={-1,-1,0,1,1,1,0,-1};									//老鼠走时要八方向遍历 对八方向的实现要加相应的该参数
int py[8]={0,1,1,1,0,-1,-1,-1};
int x_max=6;
int y_max=6;
int MG[6][6]={{0,0,0,1,1,0},{0,0,1,0,0,0},{0,1,0,0,1,1},
                                       {1,0,1,1,0,1},{0,1,0,1,0,1},{1,0,1,0,0,0}};
int tMG[6][6]={0};                                             //定义的迷宫副图防止在遍历迷宫时有死循环的出现
class StackNode 
{
public:
	int x;
	int y;
	bool real;
	int flage;
	int former;
	StackNode(bool realt=true,int xt=0,int yt=0,int flaget=-1,int formert=-1)
	{
		real=realt;
		x=xt;
		y=yt;
		flage=flaget;
		former=formert;
	}
};


class Stack
{
public:
	int point;
	StackNode* container[100];
	
	Stack()
	{
		point=-1;
	}
	void push(StackNode* s)
	{
		container[++point]=s;
		tMG[s->x][s->y]=1;
	}
	StackNode* pop()
	{
		if(point>-1&&point<100)
		return container[point];
		else return new StackNode(false,0,0,-1,-1);
	}
	void del()
	{
		tMG[(container[point])->x][(container[point])->y]=1;
		delete container[point];
		point--;
	}
	void display()
	{
		int temp=point;
		for(int i=0;i<=temp;i++)
		{
			cout<<"("<<(container[i])->x<<","<<(container[i])->y<<"),\t";
		}
	}
	~Stack()
	{
		int temp=point;
		for(;temp!=-1;temp--)
		{
			delete container[temp];
		}
	}
}
;
StackNode* next(StackNode *s)
{
	if(s->real==false)
		return s;
	else
	{
	while(++s->flage!=8)
	{
		if(s->flage!=s->former&&s->x+px[s->flage]>-1&&s->x+px[s->flage]<x_max&&
			s->y+py[s->flage]>-1&&s->y+py[s->flage]<y_max&&MG[s->x+px[s->flage]][s->y+py[s->flage]]!=1
			&&tMG[s->x+px[s->flage]][s->y+py[s->flage]]==0)
		{
			return new StackNode(true,s->x+px[s->flage],s->y+py[s->flage],-1,(s->flage+4)%8); 
		}		
	}
	return new StackNode(false,0,0,-1,-1);
	}
}

void main()
{
	cout<<"老鼠要跑的迷宫如下：\n";
	for(int i=0;i<6;i++)
	{
		for(int j=0;j<6;j++)
			cout<<MG[i][j]<<" ";
		cout<<endl;
	}
	//--------------------------
	int f=0;
	Stack* SC=new Stack();
	StackNode* sn=new StackNode(true,0,0,-1,-1);
	SC->push(sn);
	StackNode* stemp=SC->pop();
	while(SC->point>=0)
	{
		stemp=next(stemp);
		if(stemp->real==true)
		{
			SC->push(stemp);
			if(stemp->x==x_max-1&&stemp->y==x_max-1)
			{
				cout<<"老鼠找到出路：\n";
				f=1;
				SC->display();
				break;
			}		
		}
		else
		{SC->del();}
		stemp=SC->pop();	
	}
	cout<<endl;
if(f==0)
cout<<"该迷宫不通"<<endl;
}