devbox
2023面试高手
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

迷宫问题（栈）_迷宫问题栈

作者：2023面试高手 | 2024-06-11 14:33:49

赞

踩

迷宫问题栈

迷宫问题（栈与队列）

[问题描述]

利用栈操作实现迷宫问题求解。

[基本要求]

（1）从文件中读取数据，生成模拟迷宫地图，不少于20行20列。

（2）给出任意入口和出口，显示输出迷宫路线。

文件内容：

解题思路：

这道题和八皇后问题比较类似。八皇后问题是在满足一定条件下，在一张图中寻找皇后放置的合适位置。这里则是根据出口和入口，在一张迷宫图中寻找路线，路线上的各点需满足：不重复且不为墙壁。

我们首先从文件中读取数据，生成迷宫地图。之后找出所有的迷宫口，并选定入口和出口。从入口出发，每次都对上下左右的四个位置进行探测，若该点满足条件(不重复且不为墙壁)，则加入保存路线的栈route中（这里我们用visit[][]数组标注某一位置是否可行）。若未到达指定出口，且某一位置无法继续前进时，则将栈顶位置弹栈，处理前一位置，若仍无法继续前进，继续弹栈，直到可以前进为止。

按照此方法找到的路线即为从入口到出口的路线，路线上的各点保存在栈route中，最后打印输出包含路线的迷宫图即可。

程序代码：
  1. # include <iostream>
  2. # include <fstream>
  3. # include <string.h>
  4. # include <stack>
  5. # define maxn 30
  6. using namespace std;
  7.  
  8. //地图类型的结构体
  9. typedef struct Point {
  10.     int col;  //行
  11.     int row;  //列
  12. }Point;
  13.  
  14. //创建迷宫
  15. void Create();
  16. //打印迷宫
  17. void Print();
  18. //生成出入口
  19. void FindGate();
  20. //判断位置是否可行
  21. bool Judge(int x, int y);
  22. //走迷宫
  23. void GoMaze();
  24.  
  25. int m = 0, n = 0;      //迷宫的行、列
  26. int maze[maxn][maxn];  //迷宫地图
  27. int gate[maxn][2];     //保存迷宫出入口
  28. int vis[maxn][maxn];   //记录走过的位置
  29. //在迷宫的前进方式
  30. int way[4][2] = { {0,1},{-1,0},{1,0},{0,-1} };
  31. stack<Point>route;     //保存路线的栈
  32. int path[maxn][maxn] = { {0} };  //路线
  33.  
  34. int main()
  35. {
  36.     Create();    //创建迷宫
  37.     Print();     //打印迷宫图
  38.     int select;
  39.     while (1) {
  40.         cout << "\n开始游戏！" << endl;
  41.         FindGate();  //生成出入口
  42.         GoMaze();    //走迷宫
  43.         cout << endl;
  44.         Print();     //打印迷宫图（包含路线）
  45.         for (int i = 1; i <= m; i++) {
  46.             for (int j = 1; j <= n; j++) {
  47.                 path[i][j] = 0;
  48.                 vis[i][j] = 0;
  49.             }
  50.         }
  51.         cout << "\n是否继续游戏? (1：是 2:否)" << endl;
  52.         cout << "请输入：";
  53.         cin >> select;
  54.         if (select != 1) {
  55.             break;
  56.         }
  57.     }
  58.     cout << "\n游戏结束！" << endl;
  59.     return 0;
  60. }
  61.  
  62. //创建迷宫
  63. void Create()
  64. {
  65.     fstream file;
  66.     file.open("迷宫样例.txt", ios::in);
  67.     if (file.fail()) {
  68.         cout << "文件打开失败" << endl;
  69.         exit(0);
  70.     }
  71.     char str[100];
  72.     char c;
  73.     int i = 0;
  74.     file.getline(str, 100);
  75.     while (str[i] != ' ' && i < strlen(str)) {
  76.         m *= 10;
  77.         m = m + str[i] - 48;
  78.         i++;
  79.     }
  80.     i++;
  81.     while (str[i] != ' ' && i < strlen(str)) {
  82.         n *= 10;
  83.         n = n + str[i] - 48;
  84.         i++;
  85.     }
  86.     int k = 1, j;
  87.     file.getline(str, 100);
  88.     while (!file.eof()) {
  89.         j = 1;
  90.         for (int i = 0; i < strlen(str); i = i + 2)
  91.         {
  92.             maze[k][j] = str[i] - 48;
  93.             j++;
  94.         }
  95.         k++;
  96.         file.getline(str, 100);
  97.     }
  98.     j = 1;
  99.     for (int i = 0; i < strlen(str); i = i + 2) {
  100.         maze[k][j] = str[i] - 48;
  101.         j++;
  102.     }
  103. }
  104.  
  105. //打印迷宫及路线
  106. void Print()
  107. {
  108.     for (int i = 1; i <= m; i++) {
  109.         for (int j = 1; j <= n; j++) {
  110.             if (maze[i][j]) {
  111.                 cout << "D";
  112.             }
  113.             else if (path[i][j]) {
  114.                 cout << "*";
  115.             }
  116.             else {
  117.                 cout << " ";
  118.             }
  119.         }
  120.         cout << endl;
  121.     }
  122. }
  123.  
  124. //生成出入口
  125. void FindGate()
  126. {
  127.     int k = 1;  //出入口序号
  128.     for (int i = 1; i <= m; i++) {
  129.         if (maze[i][1] == 0) {
  130.             cout << "(" << k << ")";
  131.             cout << i << " " << 1 << endl;
  132.             gate[k][0] = i;
  133.             gate[k][1] = 1;
  134.             k++;
  135.         }
  136.         if (maze[i][n] == 0) {
  137.             cout << "(" << k << ")";
  138.             cout << i << " " << n << endl;
  139.             gate[k][0] = i;
  140.             gate[k][1] = n;
  141.             k++;
  142.         }
  143.     }
  144.     for (int i = 2; i < n; i++) {
  145.         if (maze[1][i] == 0) {
  146.             cout << "(" << k << ")";
  147.             cout << 1 << " " << i << endl;
  148.             gate[k][0] = 1;
  149.             gate[k][1] = i;
  150.             k++;
  151.         }
  152.         if (maze[m][i] == 0) {
  153.             cout << "(" << k << ")";
  154.             cout << m << " " << i << endl;
  155.             gate[k][0] = m;
  156.             gate[k][1] = i;
  157.             k++;
  158.         }
  159.     }
  160. }
  161.  
  162. //判断位置是否可行
  163. bool Judge(int x, int y)
  164. {
  165.     if (x > m || x < 1 || y > n || y < 1 || maze[x][y] || vis[x][y]) {
  166.         //超过边界或该点为墙壁或上一次走过，则不通
  167.         return false;
  168.     }
  169.     else {
  170.         return true;
  171.     }
  172. }
  173.  
  174. //走迷宫
  175. void GoMaze()
  176. {
  177.     int x, y, x1, y1, x2, y2;
  178.     cout << "请输入入口序号：";
  179.     cin >> x;
  180.     x1 = gate[x][0];
  181.     y1 = gate[x][1];
  182.     cout << "请输入出口序号：";
  183.     cin >> y;
  184.     x2 = gate[y][0];
  185.     y2 = gate[y][1];
  186.     Point current;     //现在所处的位置
  187.     current.col = x1;
  188.     current.row = y1;
  189.     path[current.col][current.row] = 1;
  190.     vis[current.col][current.row] = 1;
  191.     route.push(current);  //将入口放入路线
  192.     //到达终点前会一直寻找路线
  193.     while (current.col != x2 || current.row != y2) {
  194.         int t = 0;  //判断是否可以继续前进
  195.         while (!t) {
  196.             for (int i = 0; i < 4; i++) {
  197.                 current.col = current.col + way[i][0];
  198.                 current.row = current.row + way[i][1];
  199.                 if (Judge(current.col, current.row)) {
  200.                     //可以继续前进
  201.                     t = 1;
  202.                     route.push(current);   //将该位置放入路线
  203.                     path[current.col][current.row] = 1;
  204.                     vis[current.col][current.row] = 1;
  205.                     break;
  206.                 }
  207.                 else {
  208.                     //不通
  209.                     current.col = current.col - way[i][0];
  210.                     current.row = current.row - way[i][1];
  211.                     continue;
  212.                 }
  213.             }
  214.             if (!t) {
  215.                 //若不能继续前进,则弹栈
  216.                 if (!route.empty()) {
  217.                     route.pop();
  218.                 }
  219.                 path[current.col][current.row] = 0;
  220.                 //更新当前位置
  221.                 if (!route.empty()) {
  222.                     current.col = route.top().col;
  223.                     current.row = route.top().row;
  224.                 }
  225.             }
  226.         }
  227.     }
  228. }

运行结果：

  1.        DDD    DDDDDD DDDD
  2. DDDDDD     DD      D DDDD
  3. DD     DDD DD DDDDDD DDDD
  4. DD DDD DDD D  DDDDDD DDDD
  5. DD DDDDDDD   D
  6. DD     DDDD  D DDDDDDDDDD
  7. DDDD DDD   DDD DDDDDDDDDD
  8. DDDD     D DDD DDDDDDDDDD
  9. DDDD DDD D D        DDDDD
  10. DDDD DDD D D DDDDDD DDDDD
  11. DDDD     D D    DDD DDDDD
  12. DDDDDDDDDD DDDD DDD DDDDD
  13. DDD      D DDDD DDD DDDDD
  14. DDD DDDD    D   DDD
  15. DDD DDDDDDDDD DDDDD DDDDD
  16. DDD      DDDD DDDDD DDDDD
  17. DDD DDDD DDDD DDDDD DDDDD
  18. DDD DDDD DDDD DDDDD DDDDD
  19. DDD DDDD            DDDDD
  20. DDD DDDD DD DDD DDDDDDDDD
  21. DDD         DDD DDDDDDDDD
  22. DDD DDDDDD DDDD        DD
  23. DDD DDDDDD DDDDDD DDDD DD
  24. DDD DDDDDD DDDDDD DDDD DD
  25.     DDDDDD DDDD   DDDD
  26.  
  27. 开始游戏！
  28. (1)1 1
  29. (2)5 25
  30. (3)14 25
  31. (4)25 1
  32. (5)25 25
  33. (6)1 2
  34. (7)25 2
  35. (8)1 3
  36. (9)25 3
  37. (10)1 4
  38. (11)25 4
  39. (12)1 5
  40. (13)1 6
  41. (14)1 7
  42. (15)1 11
  43. (16)25 11
  44. (17)1 12
  45. (18)1 13
  46. (19)1 14
  47. (20)25 16
  48. (21)25 17
  49. (22)25 18
  50. (23)1 21
  51. (24)25 23
  52. (25)25 24
  53. 请输入入口序号：1
  54. 请输入出口序号：5
  55.  
  56. *******DDD    DDDDDD DDDD
  57. DDDDDD*    DD      D DDDD
  58. DD*****DDD DD DDDDDD DDDD
  59. DD*DDD DDD D  DDDDDD DDDD
  60. DD*DDDDDDD   D
  61. DD***  DDDD  D DDDDDDDDDD
  62. DDDD*DDD***DDD DDDDDDDDDD
  63. DDDD*****D*DDD DDDDDDDDDD
  64. DDDD DDD D*D        DDDDD
  65. DDDD DDD D*D DDDDDD DDDDD
  66. DDDD     D*D    DDD DDDDD
  67. DDDDDDDDDD*DDDD DDD DDDDD
  68. DDD******D*DDDD DDD DDDDD
  69. DDD*DDDD*** D   DDD
  70. DDD*DDDDDDDDD DDDDD DDDDD
  71. DDD******DDDD DDDDD DDDDD
  72. DDD DDDD*DDDD DDDDD DDDDD
  73. DDD DDDD*DDDD DDDDD DDDDD
  74. DDD DDDD********    DDDDD
  75. DDD DDDD DD DDD*DDDDDDDDD
  76. DDD         DDD*DDDDDDDDD
  77. DDD DDDDDD DDDD********DD
  78. DDD DDDDDD DDDDDD DDDD*DD
  79. DDD DDDDDD DDDDDD DDDD*DD
  80.     DDDDDD DDDD   DDDD***
  81.  
  82. 是否继续游戏? (1：是 2:否)
  83. 请输入：1
  84.  
  85. 开始游戏！
  86. (1)1 1
  87. (2)5 25
  88. (3)14 25
  89. (4)25 1
  90. (5)25 25
  91. (6)1 2
  92. (7)25 2
  93. (8)1 3
  94. (9)25 3
  95. (10)1 4
  96. (11)25 4
  97. (12)1 5
  98. (13)1 6
  99. (14)1 7
  100. (15)1 11
  101. (16)25 11
  102. (17)1 12
  103. (18)1 13
  104. (19)1 14
  105. (20)25 16
  106. (21)25 17
  107. (22)25 18
  108. (23)1 21
  109. (24)25 23
  110. (25)25 24
  111. 请输入入口序号：2
  112. 请输入出口序号：4
  113.  
  114.        DDD    DDDDDD DDDD
  115. DDDDDD     DD      D DDDD
  116. DD     DDD DD DDDDDD DDDD
  117. DD DDD DDD D  DDDDDD DDDD
  118. DD DDDDDDD   D***********
  119. DD     DDDD  D*DDDDDDDDDD
  120. DDDD DDD   DDD*DDDDDDDDDD
  121. DDDD     D DDD*DDDDDDDDDD
  122. DDDD DDD D D  ******DDDDD
  123. DDDD DDD D D DDDDDD*DDDDD
  124. DDDD     D D    DDD*DDDDD
  125. DDDDDDDDDD DDDD DDD*DDDDD
  126. DDD      D DDDD DDD*DDDDD
  127. DDD DDDD    D   DDD*
  128. DDD DDDDDDDDD DDDDD*DDDDD
  129. DDD******DDDD DDDDD*DDDDD
  130. DDD*DDDD*DDDD DDDDD*DDDDD
  131. DDD*DDDD*DDDD DDDDD*DDDDD
  132. DDD*DDDD*  *********DDDDD
  133. DDD*DDDD*DD*DDD DDDDDDDDD
  134. DDD*    ****DDD DDDDDDDDD
  135. DDD*DDDDDD DDDD        DD
  136. DDD*DDDDDD DDDDDD DDDD DD
  137. DDD*DDDDDD DDDDDD DDDD DD
  138. ****DDDDDD DDDD   DDDD
  139.  
  140. 是否继续游戏? (1：是 2:否)
  141. 请输入：2
  142.  
  143. 游戏结束！

以上便是我对这道题的看法，很高兴与大家分享。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/703592
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号