#include<stdio.h>                           /*該文件包含prinf()等函數(shù)*/
#include<stdlib.h>                          /*該文件包含exit()等函數(shù)*/

typedef struct
{
	int left;                               /*向左指向的路口*/
	int forward;                            /*向前指向的路口*/
	int right;                              /*向右指向的路口*/
}InterSection;                              /*路口的結(jié)構(gòu)體定義*/            

typedef struct
{
	int mazeSize;                           /*路口個數(shù)*/
	InterSection * intSec;                  /*路口集合*/
	int Exit;                               /*出口*/
}Maze;                                      /*迷宮的結(jié)構(gòu)體定義*/

/*---------------------------------迷宮的創(chuàng)建函數(shù)------------------------------------------*/
void CreatMaze(char * filename,Maze * m)   
/*按文件Filename中存放的數(shù)據(jù)創(chuàng)建迷宮*/ 
{
	FILE * fp;
	int i;

	fp=fopen(filename,"r");                 /*打開文件*/
	if(!fp)
	{
		printf("數(shù)據(jù)文件無法打開!\n");
		return;
	}

	fscanf(fp,"%d",&m->mazeSize);           /*讀入路口個數(shù)*/

	/*建立mazeSize+1個元素的數(shù)組*/
	m->intSec=(InterSection *)malloc(sizeof(InterSection)*(m->mazeSize+1));

	for(i=1;i<=m->mazeSize;i++)             /*讀入全部路口的結(jié)構(gòu)體數(shù)值*/
		fscanf(fp,"%d%d%d",&m->intSec[i].left,&m->intSec[i].forward,&m->intSec[i].right);
	fscanf(fp,"%d",&m->Exit);               /*讀入出口數(shù)值*/


	fclose(fp);                             /*關閉文件*/
}

/*----------------------------------迷宮的路徑搜索函數(shù)----------------------------------------*/
int TravMaze(Maze * m,int currSetValue)
/*從迷宮的出口往前搜索，搜索當前路口的前一路口，直到到達迷宮的入口*/
{
	int i,p=-1;                     /*當前路口的前一路口的標號p*/

	for(i=m->mazeSize;i>0;i--)
	{


		if(m->Exit==m->intSec[i].forward||m->Exit==m->intSec[i].left||m->Exit==m->intSec[i].right)
			                        /*搜索到達迷宮的出口的前一路口p*/
		{
			p=i;                    /*賦當前路口的標號*/
			printf("%d<== ",p);     /*輸出當前路口的標號*/
			
		}

		if(p==m->intSec[i].forward||p==m->intSec[i].left||p==m->intSec[i].right)
			                        /*搜索路口p的前一路口*/
		{
			p=i;                    /*賦當前路口的標號*/
			printf("%d<== ",p);     /*輸出當前路口的標號*/
			
		}
		if(p==currSetValue) return 1;/*當搜索到入口currSetValue時，搜索成功返回1，搜索結(jié)束*/
	}
	return 0;                        /*否則搜索失敗，返回0*/
}

/*####################################主函數(shù)#################################################*/
void main(void)
{
	Maze m;
	int start=1;                     /*迷宮的入口標號*/

	CreatMaze("Maze.txt",&m);       /*打開包含迷宮問題信息的文件，創(chuàng)建迷宮問題*/
	printf("%d<== ",m.Exit);         /*顯示迷宮的出口*/
	
	if(TravMaze(&m,start))           /*求出一條走出迷宮的路徑，并輸出*/
		printf("\n此迷宮的一條通路如上所示!\n");
	else
		printf("此迷宮無通路!\n");
}