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

#include <stdio.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}   };


//***********************函數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){
	int bGetPath=0;

	//已到出口，返回“1”
	if( (m==x)&&(p==y) ){
		printf("%d,%d\n",x,y);
		return 1;
	}
	
	//表記該位置已走過
	mark[x][y]=1;

	//如果該位置是墻，返回0
	if(!maze[x][y]) return 0;

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

	if(bGetPath){
		printf("%d,%d\n",x,y);
		return 1;
	}
	
	return 0;
}


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