【数据结构】10分钟教你用栈求解迷宫老鼠问题超详细教程附C++源代码
【数据结构】10分钟教你用栈求解迷宫老鼠问题超详细教程附C++源代码
问题描述
给定一张迷宫地图和一个迷宫入口，然后进入迷宫探索找到一个出口。如下图所示：
该图是一个矩形区域，有一个入口和出口。迷宫内部包含不能穿越的墙壁或者障碍物。这些障碍物沿着行和列放置，与迷宫的边界平行。迷宫的入口在左上角，出口在右下角。
问题分析
- 首先要有一张迷宫地图，地图由两部分组成： （1）一是迷宫中各处的位置坐标， （2）二是迷宫各位置处的状态信息，即该处是墙还是路
所以，该迷宫地图可由一个二维数组来表示。数组的横纵坐标表示迷宫各处的位置坐标，数组元素表示各位置处的状态信息。
2.在这里，假定：
（1）迷宫地图是m*n的，即二维数组是m行n列的。 （2）在迷宫中用1表示墙，用0表示路。当然，为了便于标识，我们后面还会用其他数字代表更多含义。
因此，迷宫的地图一个刻画如下：
现在我们要找一条从入口到出口的路径。路径是一个由位置组成的序列，每一个位置都没有障碍，并且除入口外，路径上的每一个位置都是前一个位置在东西南北方向上相邻的一个位置。
不过，考虑到边界问题不太好处理。我们做这样的工作，在地图外围加一层围墙，给它全部填上1。这样，在处理各个坐标时，都没有差别了。这样一来便大大简化了我们的工作。
下面我们要编写程序求解这个问题。
程序设计
这次还是采用一个简单的模块化来设计这个程序。那么主要有下面几个模块：
- 显示欢迎信息
- 初始化工作
- 生成地图
- 找路
- 打印地图和路径
下面我们分别完成这些功能。
显示欢迎信息
这个模块就很简单了，输出一些信息提醒使用者就行，主要是为了增加程序的友好性而设置的。大家根据自己的需要自行发挥。例如我的就很随便了：
1void welcome()
2{
3 cout << "welcome to RAT IN MAZE" << endl;
4 system("pause");
5 system("cls");
6}
初始化工作
这个主要是设置一些全局变量的取值和完成内存的分配，地图的存储还是从堆上分配内存比较好。因为一般来说，考虑到地图可能会很大，这样需要的存储空间就很多了。在这里一并把相关的全局变量给讲解了吧。
1typedef struct
2{
3 int row;
4 int col;
5}POSITION;
6
7
8const POSITION maze_size = { 20 , 60 };
9
10int ** const maze = new int*[maze_size.row + 2];
11
12stack<POSITION> path;
13POSITION offset[4];//direction- POSITION结构体 坐标结构体变量类型，很容易理解，有两个成员变量：x坐标和y坐标。
- maze_size 定义地图的大小，实际分配内存的时候，我们还需要考虑地图边界也需要存储空间。总之，我们的地图坐标范围是1 to maze_size。
- maze 二位数组，存储地图，分配的时候+2是用来存储边界的。至于const则是约束指针不改变。不过我们的地图数组是根据maze_size大小动态分配的。
- path 用来存路径的。
- offset 用来设置位置偏移的。比如我们当前位置是(row = 1, col = 1)，那么通过row + 1便可往下走，row - 1就是往上走。col + 1往右走，col - 1 往左走。等等。通过坐标加减offset偏移，便可以移动了。
1void init()
2{
3 //偏移
4 offset[0].row = 0; offset[0].col = 1; //right
5 offset[1].row = 1; offset[1].col = 0; //down
6 offset[2].row = 0; offset[2].col = -1; //left
7 offset[3].row = -1; offset[3].col = 0; //up
8
9 //maze = new int*[maze_size.row + 2];
10 for (int i = 0; i < maze_size.row + 2; i++)
11 {
12 maze[i] = new int[maze_size.col + 2];
13 }
14}这个代码就是设置偏移的数值，以及动态分配地图数组了。
生成地图
生成地图还是根据地图尺寸，然后随机设置障碍。不过要注意障碍出现的概率设置得小一点，不然地图一般无解。可以用rand()随机数来做。这一步也要把围墙设置好。
1//地图范围1 - maze_size 有围墙
2void randomMaze()
3{
4 int i, j, rate;
5
6 for (i = 0; i < maze_size.row + 2; i++)
7 {
8 for (j = 0; j < maze_size.col + 2; j++)
9 {
10 //设置围墙
11 if ((i == 0) || (i == maze_size.row + 1) || (j == 0) || (j == maze_size.col + 1))
12 {
13 maze[i][j] = 1;
14 }
15 else
16 {
17 rate = rand() % 10+1;
18 if (rate <= 3)
19 {
20 maze[i][j] = 1;//随机生成障碍
21 }
22 else
23 {
24 maze[i][j] = 0;
25 }
26 }
27 }
28 }
29 //最后保证起点和终点能走
30 maze[1][1] = maze[maze_size.row][maze_size.col] = 0;
31}找路
这个是整个程序设计的核心功能，没有之一。在写代码之前，我们需要弄明白，到底怎么找路呢？
- 首先，把迷宫入口作为当前位置。
- 如果当前位置是迷宫出口，那么已经找到一条路径了，程序结束。
- 如果当前位置不是出口，则在当前位置放置障碍物，表示这里已经来过，防止下次又重复绕回来。然后检查相邻位置是否能走。
- 如果一个相邻位置能走，就移动到这个位置上。然后在新的位置上重新开始寻找出口。如果不能走，就尝试下一个相邻位置。
- 如果所有的相邻位置都不能走了，则回退到上一个位置，重新选择上一个位置的其他相邻位置，继续探索。
- 如果所有的相邻位置都被探索过了，仍然找不到路径，那说明这个迷宫不存在这样的路径。
例如，下面的地图：
图8-9
好了，说了这么多，相信大家已经了解得差不多，并且跃跃欲试了。
1bool findPath()
2{
3 POSITION here; //当前位置
4 here.row = here.col = 1;
5 maze[1][1] = 3; //放置障碍，防止回来
6 int option = 0; //next step
7 const int lastOption = 3;
8
9 //find a path
10 while ( here.row != maze_size.row || here.col != maze_size.col)
11 {
12 //not reach the end
13 int r, c;
14 while (option <= lastOption)
15 {
16 r = here.row + offset[option].row;
17 c = here.col + offset[option].col;
18 if (maze[r][c] == 0)
19 {
20 break;
21 }
22 option++;//next choice
23 }
24
25 //相邻的位置能走？
26 if (option <= lastOption)
27 {
28 path.push(here);
29 here.row = r;
30 here.col = c;
31 maze[r][c] = 3; //走过了
32 option = 0;
33 }
34 else
35 {
36 if (path.empty())
37 {
38 return false;
39 }
40 //go back
41 maze[here.row][here.col] = 3; //此路不可通
42 here = path.top();
43 path.pop();
44 option = 0;
45 }
46 }
47
48 maze[maze_size.row][maze_size.col] = 2;
49
50 return true;
51}相关代码如上面所示，结合前面的讲解，相信大家也能看懂。
打印地图和路径
这个功能就比较简单了，主要是根据maze的信息，生成相应的地图显示出来给大家直观的看到。对于maze里面存的数值，我们也可以作一个小小的规定：
- 0 表示位置可通行。
- 1 表示位置有障碍。
- 2 表示该位置处在找到的路径上面。
- 3 探索过程中放置的障碍物。这个障碍物和1表示的障碍物不同的是，这个障碍我们放置的，和生成地图时的固定障碍物不同。因此还是要区分开来的。
然后打印的时候，遍历maze数组，遇到：
- 0 打印空格。
- 1 打印*号。
- 2 打印#号，并且设置下颜色。
- 3 还是打印空格。（或者根据自己的喜好打印另外的符号，这样就可以把探索过的所有位置显示出来。）
最后在打印最终的地图和路径之前，如果找到一条路径。我们还要根据path中的路径，在maze里面设置好相应的值，才做最终的输出：
1void setPathOnMaze()
2{
3 POSITION pos;
4 while (!path.empty())
5 {
6 pos = path.top();
7 path.pop();
8 maze[pos.row][pos.col] = 2;//路径
9 }
10}
11
12然后，可以开始输出我们的地图了。具体代码：
1void outputMaze()
2{
3 int i, j;
4 for (i = 0; i < maze_size.row + 2; i++)
5 {
6 for (j = 0; j < maze_size.col + 2; j++)
7 {
8 if (maze[i][j] == 1)
9 {
10 cout << "*";
11 }
12 else if ((maze[i][j] == 0) || (maze[i][j] == 3))
13 {
14 cout << " ";
15 }
16 else
17 {
18 HANDLE hOut;
19 hOut = GetStdHandle(STD_OUTPUT_HANDLE);
20 SetConsoleTextAttribute(hOut,FOREGROUND_GREEN | FOREGROUND_INTENSITY);
21 cout << "#";
22 SetConsoleTextAttribute(hOut, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
23 }
24 }
25 cout << endl;
26 }
27}最终效果
- 没有找到路的情况：
- 找到了路径：
