//使用回溯法求解迷宮問題migong.cpp
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<fstream.h>
//路口的結構體定義
typedef struct
{int left;
 int forward;
 int right;
}InterS;
//迷宮類定義與實現
class Maze
{private:
  int mazeSize;//路口個數
  int Exit;    //出口
  InterS *intSec;//路口集合
 public:
 //構造函數
  Maze(char *filename);
 //搜索函數
  int TravMaze(int intSecV);
};
Maze::Maze(char *filename)
{ifstream fin;
 fin.open(".\\Maze1.dat",ios_base::in);//打開文件
 if(!fin)
 {cerr<<"數據文件無法打開!\n";exit(1);}
 fin>>mazeSize;//讀入路口個數
 intSec=new InterS[mazeSize+1];//建立路口集合數組
 for(int i=1;i<=mazeSize;i++)//讀入所有路口的結構體數值
  fin>>intSec[i].left>>intSec[i].forward>>intSec[i].right;
 fin>>Exit; //讀入出口號碼
 fin.close();//關閉文件
}
int Maze::TravMaze(int intSecV)
{if(intSecV>0)
  {if(intSecV==Exit)//到達出口
    {cout<<intSecV<<"<==";//輸出路口號碼
     return 1;}
   else if(TravMaze(intSec[intSecV].left))//向左搜索
    {cout<<intSecV<<"<==";//輸出路口號碼
     return 1;}
   else if(TravMaze(intSec[intSecV].forward))//向前搜索
    {cout<<intSecV<<"<==";
     return 1;}
   else if(TravMaze(intSec[intSecV].right))//向右搜索
    {cout<<intSecV<<"<==";
     return 1;}
  }
  return 0;
}
//迷宮類的測試
void main()
{cout<<"migong.cpp運行結果:\n";
 cout<<"求解迷宮問題:\n";
 char fileName[20]={".\\Maze1.dat"};
 Maze m(fileName);
 int start=1;
 if(m.TravMaze(start))
  cout<<endl<<"此迷宮的一條通路如上輸出所示!\n";
 else cout<<"此迷宮無通路!\n";
 cin.get();
}