//程序名：labyrinth.cpp
//      程序功能：迷宮通路尋找的實現
//          作者：黃秋旋
//          日期：2008.12.20
//          版本：1.0
//      修改內容：
//      修改日期：
//      修改作者：
//對應類實現文件: labyrinth.h
//                Stack.h

#include"labyrinth.h"


////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：主函數
//函數返回值：無

void main()
{
	int i,j;
	char ch;
choice:cout<<"是否重新輸入迷宮：Y/y：是，N/n：否 \n請選擇（Y/N）：";     //選擇是否重新輸入迷宮
	cin>>ch;
	if(ch=='Y' || ch=='y') //選擇重新輸入迷宮     
	{
		cout<<"\n請輸入8行10列的迷宮矩陣，其中最外層均為“1”!\n";
lg:for(i=0;i<m+2;i++)        //輸入迷宮
			for(j=0;j<n+2;j++)
			{
				cin>>maze[i][j];
				mark[i][j]=0;       //初始化未訪問標志
			}//for
	}//if:選擇Y

	else if(ch=='N' || ch=='n')//選擇從文件中讀入迷宮
	{
		ifstream fip;
		fip.open("labyrinth.txt",ios::in|ios::binary);   //打開文件
        if(fip.fail())  //打開失敗
		{
			cout<<"文件不存在！請重新輸入迷宮！";
			goto lg;   //回到if重新輸入迷宮
		}//else if 

		int in;
			for(i=0;i<m+2;i++)
			{
				for(j=0;j<n+2;j++)
				{     
					fip>>in;      //讀取迷宮數據
					maze[i][j]=in;
					cout<<maze[i][j]<<' ';   //輸出迷宮
                    mark[i][j]=0;    //初始化未訪問標志
				
				}//for
				cout<<endl;
			}//for
		
		fip.close();   //關閉文件
	}//else if
	else   //輸出錯誤，提示重新輸入
	{
		cout<<"請重新輸入你的選擇！"; 
		goto choice;    //重新選擇讀入迷宮的方式
	}//else
	cout<<"(x,y,d)中的x，y分別表示迷宮中的坐標!"<<endl<<endl;
	cout<<"0: 向↓,1: 向↘,2: 向→, 3：向↖"<<endl<<endl;      
	cout<<"4: 向↑,5: 向↖,6: 向←, 7: 向↘" <<endl<<endl;         
	cout<<"有兩種方式輸出迷宮路徑，"<<endl<<endl;
	cout<<"Y/y:逆序（遞歸算法）,N/n:順序（非遞歸非遞歸）! \n";
    cout<<"\n請輸入你的選擇： ";   
choice1:cin>>ch;     //選擇想調用的算法
	cout<<endl;
	
	if(ch=='N' || ch=='n')   //選擇非遞歸算法
	{
		cout<<"采用順序輸出迷宮路徑: \n";
		cout<<"\nd 表示做到下一個坐標的方向!\n";
	    cout<<"\n路徑為：\n";
		Seek();    //調用尋路非遞歸函數
	}
     else if(ch=='Y' || ch=='y')   //選擇遞歸算法
	 {
		 cout<<"采用逆序輸出迷宮路徑! \n";
		 cout<<"\nd 表示從前一個坐標走到該坐標的方向\n";
		 cout<<"\n路徑為：\n";
                 mark[1][1]=1;    //加訪問標志      
         if(Seekd(1,1))   //調用遞歸時用	
	     cout<<"("<<1<<","<<1<<")"<<endl;       //尋找到通路時，輸出迷宮入口處的坐標	
	 }//else if
	 else  //輸出錯誤，提示重新輸入
	 {
		 cout<<"\n輸入錯誤，請重新輸入你的選擇：";
		 goto choice1;     //重新選擇算法
	 }
                    
}


????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????
//程序名：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


????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????
//程序名：Stack.h
//程序功能：棧類的頭文件
//作者：黃秋旋
//日期：2008.12.20
//版本：1.0
//修改內容：
//修改日期：
//修改作者：
//對應類實現文件: labyrinth.h
//對應主程序文件: labyrinth.cpp



#include<iostream.h>
#include<stdlib.h>

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


struct items         //存儲通路坐標信息的結構體
{
	int x,y,d;
};

typedef items Type;


struct Node         //棧節點的結構體
{
	Type data; 
	Node *next;
};

class Stack      //棧類定義
{
private:
	Node *atop;

public:
	Stack(){atop=NULL;};  //構造函數
	~Stack();   //析構函數
	Type top();  //取棧頂函數
	void pop();  //出棧函數
	bool empty();  //判空函數
	bool push(Type& x);  //壓棧函數
};


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：析構函數
//函數功能：釋放棧類的空間
//函數參數：無
//參數返回值：無

Stack::~Stack()
{
	Node *p;
	while(atop!=NULL)
	{
		p=atop;
		atop=atop->next;
		delete p;  //釋放節點p的空間
	}//while
};


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：取棧頂元素
//函數功能：取出棧頂元素
//函數參數：無
//參數返回值：atop->data ：棧頂元素的數據

Type Stack::top()
{
	if(atop==NULL)
		exit(1);
	else
		return (atop->data);     //返回棧頂元素的內容
};


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：出棧函數
//函數功能：使棧頂元素出棧
//函數參數：無
//參數返回值：無

void Stack::pop()
{
	if(atop==NULL) exit(1);  //當棧為空時，正常退出
	else 
	{
	    atop=atop->next;  //棧頂指針指向下一個元素
	}
};


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：判空函數
//函數功能：判斷棧是否為空
//函數參數：無
//參數返回值：bool：當棧為空時返回，否則返回0

bool Stack::empty()
{
	return atop==NULL;
};


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：壓棧函數
//函數功能：將通路數據壓入棧中
//函數參數：Type &x:表示按引用方式，將通路的實參傳給函數
//參數返回值：bool：壓棧完成時返回true

bool Stack::push(Type &x)
{
	Node *p;
	p=new Node;  //為節點指針p申請空間
	p->data=x;  //將通路信息賦給p的數據域
	p->next=atop;  //用頭插入的方式將節點p插入到棧鏈中
	atop=p;  //棧頂指針指向p
    return true;  //壓棧完成，返回true
};