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