#include "stdafx.h"
#include <windows.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <list>
#include <stack>
#include <time.h>

using namespace std;


//class:MazePos-----------------------------------------
//迷宮通道塊類型
class MazePos
{
public:
 int wx,ly; //塊的X,Y坐標(biāo) 
 int path; //塊的類型;0:空塊,-1:墻壁,1:出口路徑
 bool pass; //是否曾經(jīng)過(對墻壁無意義);false:沒有,true:曾經(jīng)過
 bool operator==(const MazePos pos)
 {
  return (wx==pos.wx && ly==pos.ly );
 };
 MazePos operator=(const MazePos pos)
 {
  
  wx=pos.wx;
  ly=pos.ly;
  pass=pos.pass;
  path=pos.path;
  return *this;
 };
};
//End:MazePos---------------------------------------


//class:SElemType-----------------------------------------
//輔助棧元素類型
class SElemType
{
public:
 int ord; //迷宮通道塊路徑上的序號
 MazePos seat;  //通道塊在迷宮中的位置坐標(biāo)
 int di;  //從此通道塊走向下一通道塊的方向
    //0:無效,1:東,2:南,3:西,4:北
 bool operator==(const SElemType et)
 {
  return (seat==et.seat); 
 };
 SElemType operator=(const SElemType et)
 {
  ord =et.ord ;
  seat =et.seat ;
  di =et.di ;
  return (*this);
 };
};
//End:SElemType--------------------------------------


//struct:MazeMap-------------------------------------
//由通道塊組成的迷宮地圖
#define MAPWIDTH 10
#define MAPHEIGHT 10

typedef struct MazeMap
{
 //由通道塊矩陣構(gòu)成
 MazePos mazemap[MAPWIDTH][MAPHEIGHT];
}MazeMap;
//End:MazeMap---------------------------------------


//struct::MazeWay----------------------------------------
//輔助出口路徑鏈表元素類型
typedef struct MazeWay
{
 int wx,ly;
}MazeWay;
//End:MazeWay--------------------------------------------


//Class:Maze----------------------------------------
//主體類,迷宮路徑問題求解
class Maze
{
public:
 Maze(int width=MAPWIDTH,int height=MAPHEIGHT); //生成迷宮地圖
 ~Maze();
 void DoMaze(); //找出出口路徑并顯示
private:
 bool InitOK; //初始化成功標(biāo)志
 MazeMap map; //迷宮地圖
 MazePos start,end; //迷宮的入口和出口
 bool FindPath(); //主要函數(shù),尋找出口路徑
 list<MazeWay> mazeway; //存放出口路徑的臨時鏈表
 void RandMap(); //隨機生成迷宮地圖函數(shù)
 bool CreateMap(bool init); //在初始和找到出口路徑后生成相應(yīng)地圖函數(shù)
 bool pass(MazePos curpos); //當(dāng)前路徑通道塊是否可通(即是不是未經(jīng)過的空塊)
 MazePos NextPos(MazePos curpos,int di); //取得當(dāng)前通道塊當(dāng)前方向上的下一個通道塊
 bool Invalide(SElemType e); //使當(dāng)前通道塊標(biāo)記為不可通
 void DisplayMaze(); //顯示迷宮地圖

};

Maze::Maze(int width,int height)
{
 //
 //隨機生成迷宮地圖
 CreateMap(true);
 //顯示地圖
 DisplayMaze();
}

Maze::~Maze()
{
 //Add codes here
}

bool Maze::FindPath ()
{
 //
 //尋找出口,并生成出口路徑鏈表
 if(InitOK)
 {
  //MazeStack mstack;
  stack<SElemType,list<SElemType> > mstack;
  MazePos curpos=start; 
  int curstep=1; //經(jīng)過的步數(shù)
  MazeWay mw; //出口路徑塊元素
  unsigned mwsize=mazeway.size (); //為顯示運行過程而設(shè)
  do
  {
   if(pass(curpos))
   {
    //如果當(dāng)前位置可通(即是未走過的空塊)

    //封裝棧元素,將當(dāng)前位置進棧
    SElemType e;
    e.ord =curstep;
    e.seat =curpos;
    e.di =1;
    mstack.push (e);

    //保存當(dāng)前位置到出口路徑鏈表
    mw.wx =e.seat .wx ;
    mw.ly =e.seat .ly ;
    mazeway.push_back (mw);


    //如果是出口,則結(jié)束
    if(curpos==end)
     return true;

    //不然就將得到下一個通道塊
    curpos=NextPos(curpos,e.di );
    curstep++;
   }
   else
   {
    //當(dāng)前位置不可通,則在棧內(nèi)找到下一個位置
    if(!mstack.empty())
    {
     SElemType e;
     e=mstack.top ();
     mstack.pop ();
     
     //調(diào)整出口路徑鏈表
     mazeway.pop_back ();

     while((e.di==0 || e.di ==4) && !mstack.empty ())
     {
      Invalide(e);  //標(biāo)記刻通道塊不能通過
      e=mstack.top ();
      mstack.pop (); //退回一步

      //調(diào)整出口路徑鏈表
      mazeway.pop_back ();

     }
     if(mstack.empty ())
      return false;
     else if( e.di<5)
     {
      e.di++;
      e.di=e.di%5;

      mstack.push (e);

      //保存當(dāng)前位置到出口路徑鏈表
      mw.wx =e.seat .wx ;
      mw.ly =e.seat .ly ;
      mazeway.push_back (mw);

      curpos=NextPos(e.seat ,e.di );
     }
     
    }
   }
   ///*//顯示運行過程
   if(mwsize!=mazeway.size () )
   {
    CreateMap(false);
    DisplayMaze();
    mwsize=mazeway.size ();
    Sleep(800); //要包含windows.h頭文件
   }
   //*
  }while(!mstack.empty ());
 }
 return false;
}

MazePos Maze::NextPos(MazePos curpos,int di)
{
 //
 MazePos pos;
 switch(di)
 {
 case 1:
  pos=map.mazemap [curpos.wx+1][curpos.ly ] ;
  break;
 case 2:
  pos=map.mazemap [curpos.wx][curpos.ly+1 ] ;
  break;
 case 3:
  pos=map.mazemap [curpos.wx-1][curpos.ly] ;
  break;
 case 4:
  pos=map.mazemap [curpos.wx][curpos.ly-1] ;
  break;
 }
 return pos;
}

bool Maze::pass(MazePos curpos)
{
 //
 //通過MazePos類型參數(shù)傳遞的信息檢查MazeMap map;
 if(curpos.wx <0 || 
  curpos.wx >=MAPWIDTH || 
  curpos.ly <0 || 
  curpos.ly >=MAPHEIGHT)
  return false;
 return (map.mazemap [curpos.wx ][curpos.ly ].path ==0 && 
   map.mazemap [curpos.wx ][curpos.ly ].pass ==false );
  
}

void Maze::DoMaze ()
{
 //
 if(!InitOK)
  return;
 if(FindPath())
 {
  CreateMap(false);
  DisplayMaze();
 }
 else
 {
  cout<<endl<<"NO PATH!"<<endl;
 }
}

void Maze::RandMap ()
{
 //
 //只能生成從左上到右下的迷宮地圖
 MazeWay curway; //隨機生成的當(dāng)前正處理的出口路徑塊(組成mw)
 list<MazeWay> mw; //隨機生成的出口路徑(由curway組成)
 list<MazeWay>::iterator iter; //容器適配器

 curway.wx =0;
 curway.ly =1;
 mw.push_back (curway);

 curway.wx ++;
 mw.push_back (curway);

 srand(time(0)); //取得當(dāng)前時間作為隨機數(shù)種子

 while(curway.wx <MAPWIDTH-1 && curway.ly <MAPHEIGHT-1)
 {
  if(rand()%2==1)
  {
   //生成隨機X坐標(biāo)上的路徑塊
   curway.wx ++;
   
   mw.push_back (curway);
  }
  else
  {
   //生成隨機Y坐標(biāo)上的路徑塊
   curway.ly ++;
   mw.push_back (curway);
  }
 }

 srand(time(0));
 for(int y=0;y<MAPHEIGHT;y++)
 {
  for(int x=0;x<MAPWIDTH;x++)
  {
   //填充每個通道塊
   map.mazemap [x][y].wx =x;
   map.mazemap [x][y].ly =y;
   map.mazemap [x][y].pass =false;
   if(x==0||y==0||x==MAPWIDTH-1||y==MAPHEIGHT-1)
   {
    //生成四周墻壁
    map.mazemap [x][y].path =-1;
    //map.mazemap [x][y].pass =true;
   }
   else
   {
    if(rand()%10>=6) //數(shù)值越小,墻壁越多
    {
     map.mazemap [x][y].path =-1; //隨機生成墻壁
     //map.mazemap [x][y].pass =true;
    }
    else
    {
     map.mazemap [x][y].path =0; //生成空的通道塊
     //map.mazemap [x][y].pass =false;
    }
   } 
  }
 }
 //生成出口路徑
 for(iter=mw.begin ();iter!=mw.end ();iter++)
 {
  map.mazemap [(*iter).wx ][(*iter).ly ].path =0;
  //map.mazemap [(*iter).wx ][(*iter).ly ].pass =false;
 }
 //生成入口和出口

 start=map.mazemap [mw.front ().wx][mw.front ().ly];
 end=map.mazemap [mw.back ().wx][mw.back ().ly];
 //初始化成功
 InitOK=true;
}

bool Maze::CreateMap (bool init)
{
 //
 if(init)
 {
  RandMap();
 }
 else
 {
  for(int y=0;y<MAPHEIGHT;y++)
   for(int x=0;x<MAPWIDTH;x++)
   {
    if(map.mazemap [x][y].path ==0)
     map.mazemap [x][y].pass =0;
   }
  list<MazeWay>::iterator  iter;
  for(iter=mazeway.begin ();iter!=mazeway.end ();iter++)
  {
   map.mazemap [(*iter).wx][(*iter).ly ].path =1; 
  }
 }
 return true;
}

bool Maze::Invalide (SElemType e)
{
 //
 //通過SElemType類型參數(shù)傳遞的信息修正MazeMap map;
 if(e.seat .wx<0 ||
  e.seat .wx>=MAPWIDTH ||
  e.seat .ly<0 ||
  e.seat .ly>=MAPHEIGHT)
  return false;
 map.mazemap [e.seat .wx][e.seat .ly ].pass =true; 
 return true;
}

void Maze::DisplayMaze ()
{
 //
 cout<<endl;
 for(int y=0;y<MAPHEIGHT;y++)
 {
  for(int x=0;x<MAPWIDTH;x++)
  {
   switch (map.mazemap [x][y].path)
   {
   case -1:
      cout<<"█";break; //墻壁圖案
   case 0:
      cout<<"  ";break; //空塊圖案
   case 1:
      cout<<"==";break; //出口路徑圖案
   }
    
  }
  cout<<endl;
 }
 cout<<endl; 
}
//End:Maze----------------------------------------

//main--------------------------------------------
//主函數(shù),迷宮求解演示
int main(int argc, char* argv[])
{
 //
 cout<<"下面是隨機生成的迷宮:"<<endl;
 Maze mymaze; //生成迷宮
 cout<<"按任意鍵演示迷宮解法!"<<endl;
 system("pause");
 mymaze.DoMaze (); //生成出口路徑
 cout<<"演示結(jié)束."<<endl;
 system("pause");
 return 0;
}
//End:main--------------------------------------------