goal00001111

/*
  Name: 迷宮類
  Copyright:始發于goal00001111的專欄；允許自由轉載，但必須注明作者和出處
  Author:goal00001111
  Date: 20-05-10 15:33
  Description:
 1。建立迷宮（外圍建筑圍墻），可選擇人工創建迷宮或計算機隨機創建迷宮，還可修改迷宮
 2。設置入口和出口。
 3。尋找最短路徑，分別采用了廣度搜索，深度搜索（包括遞歸和非遞歸形式）
 4。若找到可行路徑，打印路徑，否則報告錯誤。
*/

#include <iostream>
#include <time.h>
using namespace std;

const int M = 20;  //最大行數
const int N = 20;   //最大列數
enum {OPEN, CLOSE, PASSED, ROAD=-1}; //分別表示該點通，不通，已走和屬于所選路徑

class MiGong{
      struct stype{//存儲每個路徑點的有關數據；橫坐標，縱坐標和其前驅在數組中的位置
            int x;
            int y;
            int pre;//在廣度搜索中用來指向前驅，在深度搜索中用來表明目前所指的方向
      } way[M*N];

      int zx[4];//存儲東南西北四個方向所對應的x的值
      int zy[4];//存儲東南西北四個方向所對應的y的值
      int begin[2];//存儲入口坐標
      int end[2]; //存儲出口坐標
      int map[M+2][N+2];//存儲迷宮地圖
      int c_map[M+2][N+2];//存儲迷宮地圖拷貝
public:
      MiGong(); //構造函數，建立一個處處都關閉的迷宮

      void BuildMiGong(); //建立迷宮地圖
      void PerfectMiGong();//修正迷宮地圖
      void CopyMiGong();  //拷貝迷宮地圖

      void GetBegin();//創建入口坐標
      void GetEnd(); //創建出口坐標
      bool IsBegin(int x, int y);//判斷該點是否為入口
      bool IsEnd(int x, int y); //判斷該點是否為出口

      bool ExtentSearchWay(); //尋找路徑：廣度搜索
      void PutQueue(int rear);//把隊列路徑顯示到迷宮中
     
      bool DeepSearchWay(); //尋找路徑：深度搜索
      bool Search(int x, int y);//深度搜索遞歸子函數
     
      bool DeepSearchWay_2(); //尋找路徑：深度搜索
      void PutStack(int top); //把棧路徑顯示到迷宮中

      void PrintMiGong();//輸出迷宮地圖
      void PrintWay();//輸出運動路徑
};

MiGong::MiGong()//構造函數，建立一個處處都關閉的迷宮
{
      for (int i=0; i<M+2; i++)
            for (int j=1; j<=N; j++)
            {
                  if (i==0 || i==M+1)
                        map[i][j] = j;
                  else
                        map[i][j] = CLOSE;
            }
      for (int i=0; i<M+2; i++)
           map[i][0] = i;
      for (int i=0; i<M+2; i++)
           map[i][N+1] = i;

      zx[0]=1; zx[1]=0; zx[2]=-1; zx[3]=0;
      zy[0]=0; zy[1]=-1;zy[2]=0;  zy[3]=1;
}

void MiGong::GetBegin()//創建入口坐標
{
      do{
            cout << "請輸入入口坐標：" << endl;
            cin >> begin[0];
            cin >> begin[1];
      } while (begin[0]<1 || begin[0]>M || begin[1]<1 || begin[1]>N);
}
void MiGong::GetEnd()//創建出口坐標
{
      do{
            cout << "請輸入出口坐標：" << endl;
            cin >> end[0];
            cin >> end[1];
      } while (end[0]<1 || end[0]>M || end[1]<1 || end[1]>N);
}
bool MiGong::IsBegin(int x, int y)//判斷該點是否為入口
{
      return (x==begin[0] && y==begin[1]) ? 1 : 0;
}
bool MiGong::IsEnd(int x, int y)//判斷該點是否為出口
{
      return (x==end[0] && y==end[1]) ? 1 : 0;
}

void MiGong::BuildMiGong() //建立迷宮地圖
{
      cout << "請選擇建立迷宮的方法： 輸入m表示人工建立，輸入c表示計算機建立" << endl;
      char choice;
      do{
            cin >> choice;
      } while (choice != 'm' && choice != 'c');

      if (choice == 'm')
      {
            cout << "請輸入迷宮地圖，0表示通，1表示不通" << endl;
            for (int i=1; i<=M; i++)
                  for (int j=1; j<=N; j++)
                        cin >> map[i][j];
      }
      else
      {
            srand( (unsigned) time(NULL));
            for (int i=1; i<=M; i++)
                  for (int j=1; j<=N; j++)
                        map[i][j] = rand() % 2;
      }
}
void MiGong::PerfectMiGong()//修正迷宮地圖
{
      int i, j;
      char choice;
      do{
            do{
                  cout << "請輸入需要修改的坐標：（輸入0，0結束）" << endl;
                  cin >> i;
                  cin >> j;
            } while (i<0 || i>M || j<0 || j>N);
            fflush(stdin);
            if (i!=0 && j!=0)
            {
                  do{
                        cout << "打開該點輸入o，關閉該點輸入c" << endl;
                        cin >> choice;
                        fflush(stdin);
                  } while (choice != 'c' && choice != 'o');
                  if (choice == 'o')
                        map[i][j] = OPEN;
                  else
                        map[i][j] = CLOSE;
                  PrintMiGong();
            }
      } while (i!=0 && j!=0);
}
void MiGong::CopyMiGong()//拷貝迷宮地圖
{
      for (int i=0; i<M+2; i++)
            for (int j=0; j<N+2; j++)
                  c_map[i][j] = map[i][j];
}

void MiGong::PrintMiGong()//輸出迷宮地圖
{
      for (int i=0; i<M+2; i++)
      {
            for (int j=0; j<N+2; j++)
            {
                  if (i==0 || i==M+1 || j==0 || j==N+1)
                  {
                        if (map[i][j] < 10)
                              cout << 0;
                        cout << map[i][j];
                  }
                  else if (OPEN == map[i][j])
                        cout << ' ' << ' ';
                  else
                        cout << '#' << '#';
            }
            cout << endl;
      }
}
void MiGong::PrintWay() //輸出運動路徑
{
    int count = 0;
      for (int i=0; i<M+2; i++)
      {
            for (int j=0; j<N+2; j++)
            {
                  if (i==0 || i==M+1 || j==0 || j==N+1)
                  {
                        if (c_map[i][j] < 10)
                              cout << 0;
                        cout << c_map[i][j];
                  }
                  else if (ROAD == c_map[i][j])
                  {
            count++;
                        cout << char(2) << char(2);
      }
                  else if (OPEN == c_map[i][j])
                        cout << ' ' << ' ';
                  else
                        cout << '#' << '#';
            }
            cout << endl;
      }
      cout << "共" << count << "步" << endl;
}

bool MiGong::ExtentSearchWay()//尋找路徑：廣度搜索
{
      CopyMiGong();

      int front = 0; //隊首
      int rear = 0;  //隊尾
      bool find = false; //判斷是否找到路徑

      way[0].x = begin[0];
      way[0].y = begin[1];
      c_map[way[0].x][way[0].y] = PASSED; //該點已走過

      while (front<=rear && !find)
      {
            for (int i=0; i<4; i++)//判斷當前路徑點四周是否可通過
            {
                  int x = way[front].x + zx[i];
                  int y = way[front].y + zy[i];

                  if (c_map[x][y] == OPEN)//如果某個方向可通過，將該點納入隊列
                  {
                        rear++;
                        way[rear].x = x;
                        way[rear].y = y;
                        way[rear].pre = front;
                        c_map[x][y] = PASSED;
                  }
                  if (IsEnd(x, y)) //找到出口
                  {
                        PutQueue(rear); //把隊列路徑顯示到迷宮中
                        find = true;
                  }
            }
            front++;
      }
      return find;
}

void MiGong::PutQueue(int rear) //把隊列路徑顯示到迷宮中
{
      CopyMiGong();

      int i = rear;
      do {
            c_map[way[i].x][way[i].y] = ROAD;
            i = way[i].pre;
      } while (!IsBegin(way[i].x, way[i].y));

      c_map[begin[0]][begin[1]] = ROAD;
}

bool MiGong::DeepSearchWay()//尋找路徑：深度搜索
{
      CopyMiGong();
     
      if (Search(begin[0], begin[1]))
      {
            c_map[begin[0]][begin[1]] = ROAD;
            return true;
      }
      return false;
}

bool MiGong::Search(int x, int y)//深度搜索遞歸子函數
{
    if (c_map[x][y] != OPEN)//如果某個方向不可通過
        return false;
     
   c_map[x][y] = PASSED; 
    if (IsEnd(x, y)) //找到出口
    {
         c_map[x][y] = ROAD; 
         return true;
      }
     
      for (int i=0; i<4; i++)//判斷當前路徑點四周是否可通過
      {
         if (Search(x+zx[i], y+zy[i]))
         {
               c_map[x][y] = ROAD;
               return true;
      }
   }
   return false;
}

bool MiGong::DeepSearchWay_2()//尋找路徑：深度搜索
{
      CopyMiGong();

      int top = 0; //棧頂指針
      bool find = false; //判斷是否找到路徑

      way[0].x = begin[0];
      way[0].y = begin[1];
      way[0].pre = 0;
      c_map[way[0].x][way[0].y] = PASSED; //該點已走過

      while (top >= 0 && !find)
      {
      if (way[top].pre < 4)
      {
               int x = way[top].x + zx[way[top].pre];
               int y = way[top].y + zy[way[top].pre];

                  if (c_map[x][y] == OPEN)//如果某個方向可通過，將該點納入棧
                  {
                        top++;
                        way[top].x = x;
                        way[top].y = y;
                        way[top].pre = 0;
                        c_map[x][y] = PASSED;
                  }
                  else  //否則換個方向
                        way[top].pre++;
                       
                  if (IsEnd(x, y)) //找到出口
                  {
                        PutStack(top); //把棧路徑顯示到迷宮中
                        find = true;
                  }
            }
            else
            {
       top--;
   }
      }
      return find;
}

void MiGong::PutStack(int top) //把棧路徑顯示到迷宮中
{
      CopyMiGong();

   while (top >= 0)
      {
            c_map[way[top].x][way[top].y] = ROAD;
            top--;
      }
}

int main()
{
      MiGong obj;
      char choice;

      do{
            obj.BuildMiGong();
            obj.PrintMiGong();
            cout << "對迷宮地圖還滿意嗎？選擇此迷宮輸入y，重新選擇迷宮輸入n, 修改迷宮輸入x" << endl;
            do{
                  cin >> choice;
            } while (choice != 'y' && choice != 'n' && choice != 'x');
      } while (choice == 'n');

      if (choice == 'x') //修正迷宮地圖
            obj.PerfectMiGong();

      obj.GetBegin();  //創建入口坐標
      obj.GetEnd();  //創建出口坐標
     
      cout << "廣度搜索：" << endl;
      if (obj.ExtentSearchWay()) //如果找到迷宮路徑
            obj.PrintWay(); //輸出路徑
      else
            cout << "此路不通！" << endl;
     
   cout << "深度搜索1：" << endl;     
      if (obj.DeepSearchWay()) //如果找到迷宮路徑
            obj.PrintWay(); //輸出路徑
      else
            cout << "此路不通！" << endl;
           
      cout << "深度搜索2：" << endl;     
      if (obj.DeepSearchWay_2()) //如果找到迷宮路徑
            obj.PrintWay(); //輸出路徑
      else
            cout << "此路不通！" << endl;

      getchar();getchar();
      return 0;
}