labyrinth.h

本程序的功能是找出指定迷宫的路径

//程序名：labyrinth.h
//程序功能：寻找迷宫通路的实现程序
//作者：黄秋旋
//日期：2008.12.20
//版本：1.0
//修改内容：
//修改日期：
//修改作者：
//对应类实现文件: Stack.h
//对应主程序文件: labyrinth.cpp


#include<iostream.h>
#include"Stack.h"
#include<fstream.h>

#define m 6    //定义迷宫常量：m: 迷宫行数
#define n 8    //              n:迷宫列数
              
int mark[m+2][n+2];    //保存访问标记的数组
int maze[m+2][n+2];    //保存迷宫数据的数组
int move[8][2]={       //方向数组
	              {0,1},  //  向↓
	              {1,1},  //  向↘
	              {1,0},  //  向→
	              {1,-1}, // 向↗
               	  {0,-1}, // 向↑
	              {-1,-1},//向↖
	              {-1,0}, // 向←
				  {-1,1}  //  向↘
                 };               


///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函数名：寻找迷宫路径的递归算法
//函数功能：用递归寻找迷宫的通路
//函数参数：x:当前通路位置的横坐标
//          y:当前通路位置的纵坐标
//参数返回值：true:表示当前位置可访问时的返回值
//            false: 表示查找通路失败时的返回值

bool Seekd(int x,int y)               
{
	int i;
	int g,h;
	if((x==m)&&(y==n))   //当前位置是迷宫出口时，返回上一层递归函数
		return true;
	for(i=0;i<8;i++)    
	{
		g=x+move[i][0];                     //求出下个一位置的行、列坐标
		h=y+move[i][1];
	    if((maze[g][h]==0)&&(mark[g][h]==0))
		{
			mark[g][h]=1;                    //置mark为1，表明已访问过
		    if(Seekd(g,h))
			{
			    cout<<"("<<g<<","<<h<<","<<i<<") ";  //当下一个坐标位置可访问时，输出通路
		        return true;   //返回上一层递归函数
			}//if
		}//if
	}//for
   if((x==1)&&(y==1))  //当找不到通路时，输出提示
    	cout<<"No path!"<<endl;
   return false;    //寻找通路失败，返回false
}


////////////////////////////////////////////////////////////////////////////////////////////////
//函数名：寻找迷宫路径的非递归算法
//函数功能：利用栈，找出迷宫的通路
//函数参数：无
//参数返回值：无

void Seek()                             
{ 
    Type item;
	mark[1][1]=1;   //访问入口处坐标
	Stack s;  //逆序暂存通路信息的栈
	Stack s1; //顺序存储通路信息

	item.x=1; item.y=1; item.d=-1;        //将入口位置及方向初值-1压入栈
	s.push(item);

	while(!s.empty())   //当栈不为空时
	{	
		item=s.top();  //取出栈顶元素，寻找从改坐标出发的下个一通路坐标
		s.pop();

		int x=item.x; int y=item.y; int d=item.d+1;         //沿原位置的下个一方向前进

		while(d<8)  //深度寻找迷宫通路
		{

			if((x==m)&&(y==n))          //到达出口，将栈s中的元素逆序压入栈s1中，然后从按顺序输出，最后返回
			{
				item.x=x;
	        	item.y=y;
		        item.d=NULL;
		        s1.push(item);      //将通路坐标压入栈s1
         
			    while(!s.empty())    //将栈s中的元素逆序
				{
					item=s.top();
                    s.pop();
                    s1.push(item);   
				}//while
                 while(!s1.empty())  //输出通路
				{
					item=s1.top();
                    s1.pop();
					if((item.x==m)&&(item.y==n))
						cout<<"("<<item.x<<","<<item.y<<") ";  //输出迷宫出口坐标
					else
						cout<<"("<<item.x<<","<<item.y<<","<<item.d<<") ";      //输出通路
				 }//while
			cout<<endl;
			return;  //输出完成，返回
			}//if

			int g=x+move[d][0];                  //按方向d前进，求出下一个位置的坐标
	        int h=y+move[d][1];

			if((maze[g][h]==0)&&(mark[g][h]==0))          //对未访问的可通行的下一个位置压入栈，并将下一个位置变为当前位置，否则沿下一个方向前进
	
			{
				mark[g][h]=1;  //访问标志
                item.x=x;
	        	item.y=y;
		        item.d=d;
		        s.push(item);      //将通路坐标暂存入栈s

				x=g;
	        	y=h;
		        d=0;                  //进入新位置后，重新从初始方向向下开始                   
			}//if
			else
				d++;  //试探下一个方向的坐标
		}//while
	}//while

cout<<"No path!"<<endl;      //不存在通路
}//Seek