堆栈应用（六）：迷宫搜索

1、问题描述

迷宫（ m a z e）是一个矩形区域，它有一个入口和一个出口。在迷宫的内部包含不能穿越的墙或障碍。在图 5 - 8所示的迷宫中，障碍物沿着行和列放置，它们与迷宫的矩形边界平行。迷宫的入口在左上角，出口在右下角。图5-8 迷宫假定用 n× m的矩阵来描述迷宫，位置 ( 1 , 1 )表示入口， (n,m) 表示出口， n和m分别代表迷宫的行数和列数。迷宫中的每个位置都可用其行号和列号来指定。在矩阵中，当且仅当在位置(i,j)处有一个障碍时其值为 1 ，否则其值为 0。图 5 - 9给出了图 5 - 8中迷宫对应的矩阵描述。迷宫老鼠（ rat in a maze）问题要求寻找一条从入口到出口的路径。路径是由一组位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居（如图 5 - 1 0所示）。下面将要编写程序来解决迷宫老鼠问题。假定程序中所使用的迷宫是正方形的（即行数等入口于列数），且迷宫足够小，以便能在目标计算机的内存中描述整个迷宫。

2、设计

可以采用自顶向下的模块化方法来设计这个程序。不难看出，这个程序可以划分为三个部分：输入迷宫、寻找路径和路径输出。
2.1 输入迷宫
迷宫以矩阵的方式表示，输入方式可以选择让用户逐行输入，也可以从文件读取。

用户逐行输入：

 1 void maze::InputMaze()
 2 {
 3     
 4     for (int rows = 1; rows < n + 1; ++rows)
 5     {
 6         int flag = 1;
 7         cout << "请输入第" << rows << "行：" << endl;
 8         while (flag)
 9         {
10             for (int cols = 1; cols < n + 1; ++cols)
11             {
12                 cin >> mazem[rows][cols];
13             }
14             cout << "输入的第" << rows << "行为：";
15             for (int cols = 1; cols < n + 1; ++cols)
16             {
17                 cout << mazem[rows][cols] << " ";
18             }
19 
20             if (mazem[1][1] == 1)//检查入口
21             {
22                 cout << "入口应没有障碍物，请重新输入。" << endl;
23             }
24 
25             if (mazem[n][n] == 1)//检查出口
26             {
27                 cout << "出口应没有障碍物，请重新输入。" << endl;
28             }
29             cin.clear();
30             cin.sync();
31             cout << endl;
32             cout << "重新输入请输入1，继续请输入其他数字:" << endl;
33             
34             int temp;
35             cin >> temp;
36             if (temp == 1)
37             {
38                 flag = 1;
39             }
40             else
41             {
42                 flag = 0;
43             }
44         }
45 
46 
47     }
48 
49     cout << "输入完毕,输入的迷宫为：" << endl;
50     OutputMaze();
51 }

View Code

从文件中读取：

 1 void maze::InputMazeFromFile(const std::string& filepath)
 2 {
 3     std::ifstream input;
 4     input.open(filepath);
 5     if (input)
 6     {
 7         for (int rows = 1; rows < n + 1;++rows)
 8         {
 9             for (int cols = 1; cols < n + 1;++cols)
10             {        
11                 if (input.eof())
12                 {
13                     std::cerr << "迷宫数据不够，请添加" << endl;
14                     exit(1);
15                 }
16                 if (!(input >> mazem[rows][cols]))
17                 {
18                     std::cerr << "输入有误，迷宫应为数字" << endl;
19                     exit(1);
20                 }
21                 
22             }
23         }
24     }
25     else
26     {
27         std::cerr << "文件打开失败" << endl;
28         exit(1);
29     }
30     input.close();
31     OutputMaze();
32 }

View Code

输出迷宫：将墙壁用其他颜色标记

 1 void maze::OutputMaze()
 2 {
 3     cout << "输入的迷宫为：" << endl;
 4     for (int rows = 1; rows < n + 1;++rows)
 5     {
 6         for (int cols = 1; cols < n + 1;++cols)
 7         {
 8             //显示迷宫，墙壁用绿色显示
 9             if (mazem[rows][cols] == 1)
10             {
11                 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), BACKGROUND_INTENSITY | FOREGROUND_INTENSITY | FOREGROUND_RED | BACKGROUND_GREEN );
12             }
13             else
14             {
15                 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | BACKGROUND_RED);
16 
17             }
18             cout << mazem[rows][cols]<<" ";
19         }
20         cout << endl;
21     }
22 
23     cout << endl;
24 }

View Code

2.2、寻找路径

　思路：首先探讨如何寻找迷宫路径。首先把迷宫的入口作为当前位置。如果当前位置是迷宫出口，那么已经找到了一条路径，搜索工作结束。如果当前位置不是迷宫出口，则在当前位置上放置障碍物，以便阻止搜索过程又绕回到这个位置。然后检查相邻的位置中是否有空闲的（即没有障碍物），如果有，就移动到这个新的相邻位置上，然后从这个位置开始搜索通往出口的路径。如果不成功，选择另一个相邻的空闲位置，并从它开始搜索通往出口的路径。为了方便移动，在进入新的相邻位置之前，把当前位置保存在一个堆栈中。如果所有相邻的空闲位置都已经被探索过，并且未能找到路径，则表明在迷宫中不存在从入口到出口的路径。

使用上述策略来考察图 5 - 8的迷宫。首先把位置 ( 1 , 1 )放入堆栈，并从它开始进行搜索。由于位置( 1 , 1 )只有一个空闲的邻居 ( 2 , 1 )，所以接下来将移动到位置 ( 2 , 1 )，并在位置 ( 1 , 1 )上放置障碍物，以阻止稍后的搜索再次经过这个位置。从位置 ( 2 , 1 )可以移动到 ( 3 , 1 )或( 2 , 2 )。假定移动到位置( 3 , 1 )。在移动之前，先在位置 ( 2 , 1 )上放置障碍物并将其放入堆栈。从位置 ( 3 , 1 )可以移动到( 4 , 1 )或( 3 , 2 )。假定移动到位置 ( 4 , 1 )，则在位置 ( 3 , 1 )上放置障碍物并将其放入堆栈。从位置 ( 4 , 1 )开始可以依次移动到 (5,1) 、 (6,1) 、 ( 7 , 1 )和( 8 , 1 )。到了位置 ( 8 , 1 )以后将无路可走。此时堆栈中包含的路径从 ( 1 , 1 )至( 8 , 1 )。为了探索其他的路径，从堆栈中删除位置 ( 8 , 1 )，然后回退至位置( 7 , 1 )，由于位置 ( 7 , 1 )也没有新的、空闲的相邻位置，因此从堆栈中删除位置 ( 7 , 1 )并回退至位置( 6 , 1 )。按照这种方式，一直要回退到位置 ( 3 , 1 )，然后才可以继续移动（即移动到位置（ 3 , 2））。注意在堆栈中始终包含从入口到当前位置的路径。如果最终到达了出口，那么堆栈中的路径就是所需要的路径。
　　对于迷宫内部的位置（非边界位置），有四种可能的移动方向：右、下、左和上。对于迷宫的边界位置，只有两种或三种可能的移动。为了避免在处理内部位置和边界位置时存在差别，可以在迷宫的周围增加一圈障碍物。对于一个m× n的迷宫，这一圈障碍物将占据数组 m a z e的第0行，第 m + 1 行，第 0列和第m + 1 列。
路径查找：

 1 bool maze::FindPath()
 2 {
 3     cout << "开始查找路径..." << endl;
 4     position current = { 1, 1 };//当前位置
 5 
 6     mazem[1][1] = 3;//阻止返回入口
 7 
 8     path = new LinkedStack<position>;
 9     position offset[4];
10     offset[0].row = 0; offset[0].col = 1;//右
11     offset[1].row = 1; offset[1].col = 0;//下
12     offset[2].row = 0; offset[2].col = -1;//左
13     offset[3].row = -1; offset[3].col = 0;//上
14 
15     int option = 0;
16     int LastOption = 3;
17     while (current.row != n || current.col != n)
18     {
19         int r, c;
20         while (option <= LastOption)
21         {
22             r = current.row + offset[option].row;
23             c = current.col + offset[option].col;
24             if (mazem[r][c] == 0) break;//找到相邻未查找过路径
25 
26             option++;
27         }
28 
29         if (option <= LastOption)
30         {
31             path->Add(current);//将当前位置加入路径
32             current.row = r;
33             current.col = c;
34             mazem[r][c] = 3;//防止再次探索，并方便后期复原为0，因此与墙壁的1区分
35             option = 0;
36         }
37         else//没有路径，回溯
38         {
39             if (path->IsEmpty())//没有未探索的路径，退出
40             {
41                 return false;
42             }
43             position next;
44             path->Delete(next);//回溯到路径的上个位置
45             if (next.row == current.row)
46             {
47                 option = 2 + next.col - current.col;
48             }
49             else
50             {
51                 option = 3 + next.row - current.row;
52             }
53 
54             current = next;
55         }
56 
57     }
58     
59     cout << "查找完毕,如下图." << endl;
60     ShowPath();
61     return true;
62 }

View Code

2.3、输出路径

在这里，路径用白色背景表示，其他部分与输出矩阵时一样。

 1 void maze::ShowPath()
 2 {
 3     while (!path->IsEmpty())
 4     {
 5         position temp;
 6         path->Delete(temp);
 7         mazem[temp.row][temp.col] = 2;//路径元素改为2，便于区分
 8         //cout << temp.row << " " << temp.col << endl;
 9     }
10     mazem[n][n] = 2;
11     for (int rows = 1; rows < n + 1;++rows)
12     {
13         for (int cols = 1; cols < n + 1;++cols)
14         {
15             if (mazem[rows][cols]==2)
16             {
17                 //改变路径背景和字体颜色，红字白背景
18                 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), BACKGROUND_INTENSITY | FOREGROUND_INTENSITY | FOREGROUND_RED | BACKGROUND_RED | BACKGROUND_GREEN | BACKGROUND_BLUE);
19                 
20             }
21             else if (mazem[rows][cols] == 0 || (rows == n&&cols == n) || mazem[rows][cols] == 3)
22             {
23                 mazem[rows][cols] =0;//将前面路径查找过程中修改过的值复原
24                 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),  FOREGROUND_INTENSITY | BACKGROUND_RED );
25             }
26             else
27             {
28                 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), BACKGROUND_INTENSITY | FOREGROUND_INTENSITY | FOREGROUND_RED | BACKGROUND_GREEN);
29             }
30             cout << mazem[rows][cols] << " ";
31         }
32 
33         cout << endl;
34     }
35     //恢复黑底白字
36     SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY
37         | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
38 }

View Code

3、完整代码

maze.h:

 1 #ifndef MAZE_H
 2 #define MAZE_H
 3 #include "LinkedStack.h"
 4 #include <fstream>
 5 #include <cstdio>
 6 #include<windows.h>
 7 
 8 using std::cout;
 9 using std::cin;
10 using std::endl;
11 
12 struct position //表示位置的结构体
13 {
14     int row;
15     int col;
16 };
17 
18 
19 class maze
20 {
21 public:
22     maze(int m);
23     maze(int* matrix, int m);//直接用矩阵初始化
24     ~maze();
25     bool FindPath();//寻找从入口到出口的路径
26     void InputMaze();//逐行输入迷宫
27     void InputMazeFromFile(const std::string& filepath);//从文件读取
28     void OutputMaze();//输出迷宫地图
29     void ShowPath();//输出路径
30 private:
31     LinkedStack<position> *path;//存储路径的堆栈
32     int **mazem;//迷宫矩阵
33     int n;//迷宫大小
34 };
35 
36 
37 #endif

View Code

maze.cpp:

  1 #include "maze.h"
  2 maze::maze(int m) :n(m)
  3 {
  4     mazem = new int*[n + 2];
  5     for (int i = 0; i < n + 2; ++i)
  6     {
  7         mazem[i] = new int[n + 2];
  8     }
  9     for (int i = 0; i < n + 2;++i)
 10     {
 11         mazem[0][i] = 1;
 12         mazem[i][0] = 1;
 13         mazem[n + 1][i] = 1;
 14         mazem[i][n + 1] = 1;
 15     }
 16     
 17 }
 18 
 19 maze::maze(int* matrix, int m):n(m)
 20 {
 21     mazem = new int*[n + 2];
 22     for (int i = 0; i < n + 2; ++i)
 23     {
 24         mazem[i] = new int[n + 2];
 25     }
 26     for (int i = 0; i < n + 2; ++i)
 27     {
 28         mazem[0][i] = 1;
 29         mazem[i][0] = 1;
 30         mazem[n + 1][i] = 1;
 31         mazem[i][n + 1] = 1;
 32     }
 33 
 34     for (int rows = 1; rows < n + 1;++rows)
 35     {
 36         for (int cols = 1; cols < n + 1;++cols)
 37         {
 38             mazem[rows][cols] = *(matrix+(rows - 1)*m+cols-1);
 39         }
 40     }
 41 }
 42 
 43 maze::~maze()
 44 {
 45     if (mazem != NULL)
 46     {
 47         for (int i = 0; i < n + 2; ++i)
 48         {
 49             if (mazem[i] != NULL)
 50             {
 51                 delete[] mazem[i];
 52             }
 53         }
 54 
 55         delete[] mazem;
 56     }
 57 }
 58 
 59 bool maze::FindPath()
 60 {
 61     cout << "开始查找路径..." << endl;
 62     position current = { 1, 1 };//当前位置
 63 
 64     mazem[1][1] = 3;//阻止返回入口
 65 
 66     path = new LinkedStack<position>;
 67     position offset[4];
 68     offset[0].row = 0; offset[0].col = 1;//右
 69     offset[1].row = 1; offset[1].col = 0;//下
 70     offset[2].row = 0; offset[2].col = -1;//左
 71     offset[3].row = -1; offset[3].col = 0;//上
 72 
 73     int option = 0;
 74     int LastOption = 3;
 75     while (current.row != n || current.col != n)
 76     {
 77         int r, c;
 78         while (option <= LastOption)
 79         {
 80             r = current.row + offset[option].row;
 81             c = current.col + offset[option].col;
 82             if (mazem[r][c] == 0) break;//找到相邻未查找过路径
 83 
 84             option++;
 85         }
 86 
 87         if (option <= LastOption)
 88         {
 89             path->Add(current);//将当前位置加入路径
 90             current.row = r;
 91             current.col = c;
 92             mazem[r][c] = 3;//防止再次探索，并方便后期复原为0，因此与墙壁的1区分
 93             option = 0;
 94         }
 95         else//没有路径，回溯
 96         {
 97             if (path->IsEmpty())//没有未探索的路径，退出
 98             {
 99                 return false;
100             }
101             position next;
102             path->Delete(next);//回溯到路径的上个位置
103             if (next.row == current.row)
104             {
105                 option = 2 + next.col - current.col;
106             }
107             else
108             {
109                 option = 3 + next.row - current.row;
110             }
111 
112             current = next;
113         }
114 
115     }
116     
117     cout << "查找完毕,如下图." << endl;
118     ShowPath();
119     return true;
120 }
121 
122 void maze::InputMaze()
123 {
124     
125     for (int rows = 1; rows < n + 1; ++rows)
126     {
127         int flag = 1;
128         cout << "请输入第" << rows << "行：" << endl;
129         while (flag)
130         {
131             for (int cols = 1; cols < n + 1; ++cols)
132             {
133                 cin >> mazem[rows][cols];
134             }
135             cout << "输入的第" << rows << "行为：";
136             for (int cols = 1; cols < n + 1; ++cols)
137             {
138                 cout << mazem[rows][cols] << " ";
139             }
140 
141             if (mazem[1][1] == 1)//检查入口
142             {
143                 cout << "入口应没有障碍物，请重新输入。" << endl;
144             }
145 
146             if (mazem[n][n] == 1)//检查出口
147             {
148                 cout << "出口应没有障碍物，请重新输入。" << endl;
149             }
150             cin.clear();
151             cin.sync();
152             cout << endl;
153             cout << "重新输入请输入1，继续请输入其他数字:" << endl;
154             
155             int temp;
156             cin >> temp;
157             if (temp == 1)
158             {
159                 flag = 1;
160             }
161             else
162             {
163                 flag = 0;
164             }
165         }
166 
167 
168     }
169 
170     cout << "输入完毕,输入的迷宫为：" << endl;
171     OutputMaze();
172 }
173 
174 void maze::InputMazeFromFile(const std::string& filepath)
175 {
176     std::ifstream input;
177     input.open(filepath);
178     if (input)
179     {
180         for (int rows = 1; rows < n + 1;++rows)
181         {
182             for (int cols = 1; cols < n + 1;++cols)
183             {        
184                 if (input.eof())
185                 {
186                     std::cerr << "迷宫数据不够，请添加" << endl;
187                     exit(1);
188                 }
189                 if (!(input >> mazem[rows][cols]))
190                 {
191                     std::cerr << "输入有误，迷宫应为数字" << endl;
192                     exit(1);
193                 }
194                 
195             }
196         }
197     }
198     else
199     {
200         std::cerr << "文件打开失败" << endl;
201         exit(1);
202     }
203     input.close();
204     OutputMaze();
205 }
206 
207 void maze::OutputMaze()
208 {
209     cout << "输入的迷宫为：" << endl;
210     for (int rows = 1; rows < n + 1;++rows)
211     {
212         for (int cols = 1; cols < n + 1;++cols)
213         {
214             //显示迷宫，墙壁用绿色显示
215             if (mazem[rows][cols] == 1)
216             {
217                 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), BACKGROUND_INTENSITY | FOREGROUND_INTENSITY | FOREGROUND_RED | BACKGROUND_GREEN );
218             }
219             else
220             {
221                 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | BACKGROUND_RED);
222 
223             }
224             cout << mazem[rows][cols]<<" ";
225         }
226         cout << endl;
227     }
228 
229     cout << endl;
230 }
231 
232 void maze::ShowPath()
233 {
234     while (!path->IsEmpty())
235     {
236         position temp;
237         path->Delete(temp);
238         mazem[temp.row][temp.col] = 2;//路径元素改为2，便于区分
239         //cout << temp.row << " " << temp.col << endl;
240     }
241     mazem[n][n] = 2;
242     for (int rows = 1; rows < n + 1;++rows)
243     {
244         for (int cols = 1; cols < n + 1;++cols)
245         {
246             if (mazem[rows][cols]==2)
247             {
248                 //改变路径背景和字体颜色，红字白背景
249                 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), BACKGROUND_INTENSITY | FOREGROUND_INTENSITY | FOREGROUND_RED | BACKGROUND_RED | BACKGROUND_GREEN | BACKGROUND_BLUE);
250                 
251             }
252             else if (mazem[rows][cols] == 0 || (rows == n&&cols == n) || mazem[rows][cols] == 3)
253             {
254                 mazem[rows][cols] =0;//将前面路径查找过程中修改过的值复原
255                 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),  FOREGROUND_INTENSITY | BACKGROUND_RED );
256             }
257             else
258             {
259                 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), BACKGROUND_INTENSITY | FOREGROUND_INTENSITY | FOREGROUND_RED | BACKGROUND_GREEN);
260             }
261             cout << mazem[rows][cols] << " ";
262         }
263 
264         cout << endl;
265     }
266     //恢复黑底白字
267     SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY
268         | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
269 }

View Code

welcome.h:

1 #ifndef WELCOME_H
2 #define WELCOME_H
3 #include <iostream>
4 using std::cout;
5 using std::endl;
6 using std::cin;
7 void Welcome(int& n);
8 #endif

View Code

welcome.cpp:

 1 #include "welcome.h"
 2 
 3 void Welcome(int& n)
 4 {
 5     cout << "欢迎来到迷宫游戏！" << endl;
 6     cout << "本程序只能输入方阵" << endl;
 7     cout << "请输入迷宫的行数" << endl;
 8 
 9     cin >> n;
10 }

View Code

测试程序：

堆栈的链式实现见：堆栈的链表方式实现

 1 #include "welcome.h"
 2 #include "maze.h"
 3 
 4 int main()
 5 {
 6     
 7     int n;//迷宫行数
 8     Welcome(n);
 9     int flag;
10     cout << "请选择输入迷宫的方式：" << endl;
11     cout << "1.手动逐行输入" << endl;
12     cout << "2.从文件读取" << endl;
13     cin.sync();
14     while(!(cin>>flag))
15     {
16         std::cerr << "error:只能输入1,2选择,请重新选择" << endl;
17         cin.clear();
18         cin.sync();
19     }
20 
21     maze m(n);
22 
23     if (flag==1)
24     {
25         m.InputMaze();
26     }
27     else
28     {
29         m.InputMazeFromFile("..\Debug\maze.txt");
30     }
31     /*
32     int matrix[8][8] =
33     {
34         0, 0, 0, 0, 1, 0, 0, 0,
35         0, 1, 0, 0, 1, 0, 0, 0,
36         0, 1, 0, 0, 1, 0, 0, 0,
37         0, 1, 0, 0, 0, 1, 0, 0,
38         0, 0, 0, 1, 0, 0, 1, 0,
39         0, 0, 0, 1, 1, 0, 0, 0,
40         0, 0, 0, 0, 0, 0, 1, 0,
41         0, 0, 0, 0, 0, 0, 0, 0,
42 
43     };
44     */
45 
46     //maze m((int*)matrix,8);
47     //m.OutputMaze();
48     if (!m.FindPath())
49     {
50         cout << "没有从入口到出口的路径！" << endl;
51 
52     }
53     
54     
55     
56     system("pause");
57 
58     return 0;
59 }

View Code

输出：此处使用maze.txt作为输入，按行存储迷宫，元素之间空格隔开

输入为：

0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0
0 1 0 0 0 0 1 0 0 0
0 1 1 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 1 0 1 1 0
0 0 1 0 0 1 0 0 0 0
0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

算法复杂度：O（迷宫中空闲的位置）

注意这个方法不保证找到的路径是最短路径，从结果也可以看出。