//
//**********************程序說明*******************************
//			該程序是迷宮問題遞歸求解全部路徑的C語言代碼，
//			迷宮二維數組表示，初值與教材圖3.4一致
//			wjluo，2004年3月3日
//*************************************************************
//

#include <stdio.h>
#include "StackImplement.h"

//**********************迷宮定義**********************//
//用二維數組maze[m+2][p+2]表示迷宮
//maze[i][j]=0表示該位置是墻壁，
//maze[i][j]=1表示該位置是通路
//maze[1][1]為入口
//maze[m][p]為出口
#define m 8  //迷宮寬度
#define p 8  //迷宮長度
short int maze[m+2][p+2]={  {0,0,0,0,0,0,0,0,0,0},
							{0,1,1,0,1,1,1,0,1,0},
							{0,1,1,0,1,1,1,0,1,0},
							{0,1,1,1,1,0,0,1,1,0},
							{0,1,0,0,0,1,1,1,1,0},						
							{0,1,1,1,0,1,1,1,1,0},
							{0,1,0,1,1,1,0,1,1,0},
							{0,1,0,0,0,1,0,0,1,0},
							{0,0,1,1,1,1,1,1,1,0},
							{0,0,0,0,0,0,0,0,0,0}  };	


//***********************標志矩陣定義*********************//
//為防止重走原路，設置一個標志矩陣mark[m+2][p+2]
//所有元素初始化為0，當走到迷宮的該位置[i][j]時，將mark[i][j]置"1"
short int mark[m+2][p+2]={  {0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0}   };

//***********************兩個全局變量************************//
int PathNo=0;	//路徑數
SqStack PathS;	//用于存儲路徑的棧PathS

//***********************函數PrintPath(SqStack S);***********//
//函數功能：打印路徑
//函數參數：棧S
//返回值：返回0表示空棧棧無路徑，否則返回1
short int PrintPath(SqStack &S){
	SElemType e;

	if(StackEmpty(S)) return 0;
	
	SqStack tempS;
	InitStack(tempS);
	while(!StackEmpty(S)){
		Pop(S,e);
		Push(tempS,e);
	}
	printf("Get path %d:  ", ++PathNo);
	while(!StackEmpty(tempS)){
		Pop(tempS,e); Push(S,e);
		printf("%d,%d  ",e.x ,e.y );
	}
	printf("\n");
	return 1;
}


//***********************函數MazeRecursion(int x, int y)***********//
//函數功能：迷宮求解的遞歸算法，求解全部路徑
//          從迷宮的某一位置[i][j]開始，尋找通向出口[p][m]的一條路徑。
//		    如果找到路徑，則函數返回1；否則函數返回0。
//			最開始的試探出發點應為入口，即[1][1]
//函數參數：int x, int y分別表示迷宮的某一位置
//返回值：返回0表示未找到路徑，返回1表示找到路徑
int MazeRecursion(int x, int y){
	SElemType e;
	e.x=x; e.y=y;

	//已到出口，打印路徑，返回“1”
	if( (m==x)&&(p==y) ){
		Push(PathS,e);	PrintPath(PathS);	Pop(PathS,e); return 1;
	}
	
	//如果該位置是墻，返回0
	if(!maze[x][y]) return 0;

	//表記該位置已走過
	mark[x][y]=1;
	Push(PathS,e);

	//既然該位置是通路，則每個位置有4個方向可以走，每個方向都要試一下
	//如果某方向的下一個位置未標記（即不在當前路徑路上），則繼續往前走
	if( !mark[x][y+1] ) MazeRecursion(x,y+1);  //向右
	if( !mark[x+1][y] ) MazeRecursion(x+1,y);  //向下
	if( !mark[x][y-1] ) MazeRecursion(x,y-1);  //向左
	if( !mark[x-1][y] ) MazeRecursion(x-1,y);  //向上

	mark[x][y]=0;
	Pop(PathS,e);
	return 0;
}


//主函數：調用迷宮求解的遞歸算法MazeRecursion(1,1)從入口開始尋找全部路徑
int main(int argc, char* argv[])
{
	InitStack(PathS);
    MazeRecursion(1,1);
	DestroyStack(PathS);
	return 0;
}