迷宫问题（栈的经典应用之一）

迷宫问题，以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对信任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

太久没好好动脑，搞这个搞到头晕晕，网上有不少，看得也是头晕晕，现在这个虽然还有些不足，没办法筛选最优路径，以后学多点知识后，再改进吧。

文件"mystack.h"

#include<iostream>
using namespace std;

class pos	//迷宫中每个点的位置，所包含的数据
{
public:
	int x;
	int y;
	int dir;	//0:无效方向，1：上，2：右，3：下，4：左
};
	
class Node	//结点类
{
public:
	pos data;
	Node *next;
	friend class Stack;
};

class Stack
{
private:
	Node *head;
public:
	Stack()
	{
		head=NULL;
	}
	
	bool empty()
	{
		return (head==0);
	}

	void push(pos d)
	{
		Node *p=new Node;
		p->data=d;
		p->next=head;
		head=p;
	}

	pos top()
	{
		if(empty())
		{
			cout<<"stack is empty."<<endl;
			exit(0);
		}
		return head->data;
	}

	void pop()
	{
		Node *p=head;
		head=head->next;
		delete p;
	}
};

文件"maze.h"

#include"mystack.h"

int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//定义当前位置移动的4个方向

//初始化迷宫
int **Getmaze(int &m,int &n)
{
	int a,b;
	int **maze;
	int i=0,j=0;
	cout<<"输入迷宫的长和宽：";
	cin>>a>>b;
	m=a;
	n=b;
	
	maze=new int *[m+2];
	for(i=0;i<m+2;i++)
		maze[i]=new int[n+2];
	
	cout<<"请输入迷宫内容(0表示通，1表示不通)：";
	//i,j都从1号位置开始，因为0号和m+1以及n+1要作为围墙
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			cin>>maze[i][j];
	for(i=0;i<m+2;i++)
		maze[i][0]=maze[i][n+1]=1;
	for(i=0;i<n+2;i++)
		maze[0][i]=maze[m+1][i]=1;
	return maze;
}

//输出路线
void PrintPath(Stack p)//将p逆置回来，放在t里面
{
	cout<<"迷宫路径为\n";
	cout<<"括号内容分别表示（行，列，方向）\n";
	Stack t;
	int a,b;
	pos data;
	Node *temp;
	temp=new Node();
	temp->data=p.top();
	p.pop();
	t.push(temp->data);
	delete temp;
	while(!p.empty())
	{
		temp=new Node();
		temp->data=p.top();
		p.pop();
		//获取方向dir
		a=t.top().x-temp->data.x;
		b=t.top().y-temp->data.y;
		if(a==1) temp->data.dir=1; //方向向下，用1表示
		else if(b==1) temp->data.dir=2; //方向向右，用2表示
		else if(a==-1) temp->data.dir=3; //方向向上，用3表示
	    else if(b==-1) temp->data.dir=4; //方向向左，用4表示
		t.push(temp->data); //把新位置入栈
		delete temp;
	}

	while(!t.empty())
	{
		data=t.top();
		t.pop();
		cout<<'('<<data.x<<','<<data.y<<','; //输出行坐标，列坐标
		switch(data.dir) //输出相应的方向  
		{
		case 1:cout<<"↓)\n";break;
		case 2:cout<<"→)\n";break;
		case 3:cout<<"↑)\n";break;
		case 4:cout<<"←)\n";break;
		case 0:cout<<"end)\n";break;
		}
	}
}

//恢复原图
void Restore(int **maze,int m,int n)
{
	int i,j;
	for(i=0;i<m+2;i++)
		for(j=0;j<n+2;j++)
			if(maze[i][j]==-1)
				maze[i][j]=0;
		
}

//寻找迷宫maze中从(0,0)到(m,n)的路径
bool Mazepath(int **maze,int m,int n)
{
	Stack p,q;//p存储探索过程，q存储路径
	pos t1,t2;
	int x,y,loop;
	t1.x=1;
	t1.y=1;
	q.push(t1);
	p.push(t1);
	maze[1][1]=-1;//用-1标志此点已到达
	while(!q.empty())
	{
		t2=q.top();
		if(!(p.top().x==t2.x&&p.top().y==t2.y))
			p.push(t2);//如果有新位置入栈，则将其加入p
		
		//探索当前的点的四个相邻位置
		for(loop=0;loop<4;loop++)
		{
			x=t2.x+move[loop][0];
			y=t2.y+move[loop][1];
			
			if(maze[x][y]==0)//然后此点可通过
			{
				t1.x=x;
				t1.y=y;
				maze[x][y]=-1; //标志新位置已经到达
				q.push(t1);
			}
			if((x==m)&&(y==n))//成功到达出口
			{
				t1.x=m;
				t1.y=n;
				t1.dir=0;
				p.push(t1);
				PrintPath(p);//输出路径
				Restore(maze,m,n);//恢复原图
				return 1;
			}
		}

		//如果如果没有新路径入栈，则返回上一个位置
		if( (p.top().x==q.top().x)&&(p.top().y==q.top().y) )
		{
			p.pop();
			q.pop();
		}
	}
	return 0;
}

测试代码"main.cpp"

#include"maze.h"

int main()
{
	int m=0,n=0;
	int **maze;
	maze=Getmaze(m,n);
	if(Mazepath(maze,m,n))
		cout<<"迷宫路径搜索成功"<<endl;
	else
		cout<<"路径不存在"<<endl;
	return 0;
}