/*  Name:  迷宫的算法  Copyright:  Author:  Date: 23-04-06 20:53  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 SearchWay(); //寻找路径      void PutWay(int rear);//把路径显示到迷宫中       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() //输出路径{      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])                        cout << char(2) << char(2);                  else if (OPEN == c_map[i][j])                        cout << ' ' << ' ';                  else                        cout << '#' << '#';            }            cout << endl;      }} bool MiGong::SearchWay()//寻找路径{      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)) //找到出口                  {                        PutWay(rear);                        find = true;                  }            }            front++;      }      return find;}void MiGong::PutWay(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;} 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();  //创建出口坐标       if (obj.SearchWay()) //如果找到迷宫路径            obj.PrintWay(); //输出路径      else            cout << "此路不通！" << endl;       getchar();getchar();      return 0;}

评论