迷宫.cpp

数据结构：顺序栈

//求解迷宫问题的主程序文件
#include<iostream.h>
#include"顺序栈.h"

const m=6, n=8;
int mark[m+2][n+2];
int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //行下0，1，2，3标分别代表东，南，西，北方向
int maze[m+2][n+2]={{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,1,0,1,1},{1,1,0,0,1,1,0,0,0,1},
{1,0,0,0,0,0,0,1,1,1},{1,1,1,0,1,1,0,0,0,1},
{1,0,0,0,0,0,1,0,1,1},{1,1,0,1,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}}; //定义保存迷宫数据的数组
bool SeekPath(int m, int n)
//查找m*n迷宫中从入口(1,1)到出口(m,n)的一条通路
{
	//将入口点访问标记置为1，表示将访问它
	mark[1][1]=1;
	//定义栈并初始化
	StackSq S;
	InitStack(S, 5);
	//定义temp为进出栈的变量
	items temp;
	//将入口点位置及方向初值-1压入栈
	temp.x=1; temp.y=1; temp.d=-1;
	Push(S,temp);
	//循环处理，直到栈空为止
	while(!EmptyStack(S))
	{
		//退栈，即从查找的路径中退回一步
		temp=Pop(S);
		//沿着原位置的下一个方向前进
		int x=temp.x; int y=temp.y; int d=temp.d+1;
		while(d<4)
		{
			//到达出口，按逆序输出路径中每个位置的坐标，然后返回
			if(x==m && y==n)
			{
				cout<<'('<<m<<','<<n<<')'<<' ';
				while(!EmptyStack(S)){
					temp=Pop(S);
					cout<<'('<<temp.x<<','<<temp.y<<')'<<' ';
				}
				cout<<endl;
				return true;
			}
			//按方向d前进，求出下一个位置的坐标
			int g=x+move[d][0]; int h=y+move[d][1];
			//对未访问过的可通行的下一个位置，应将当前位置进栈，
			//并将下一个位置变为当前位置，否则沿下一个方向前进
			if(maze[g][h]==0 && mark[g][h]==0)
			{
				mark[g][h]=1;
				temp.x=x; temp.y=y; temp.d=d;
				Push(S,temp);
				x=g; y=h; d=0;
				//进入一个新位置后，重新从初始方向东开始
			}
			else
				d++;   //沿下一个方向前进
		}
	}
	return false;  //没有通路返回假
}

void main()
{
	int i, j;
	//初始化mark数组
	for(i=0; i<m+2; i++)
		for(j=0;j<n+2; j++)
			mark[i][j];
		//调用求解迷宫的非递归算法，结果被赋给b
		bool b=SeekPath(m,n);
		//当b为假时，表明没有通向终点的路径，应打印出没有路径的信息
		if(!b) cout<<"从入口到出口没有通路！"<<endl;
}