首页 > 代码库 > 堆栈应用（六）：迷宫搜索
堆栈应用（六）：迷宫搜索
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 else41 {42 flag = 0;43 }44 }45 46 47 }48 49 cout << "输入完毕,输入的迷宫为：" << endl;50 OutputMaze();51 }
从文件中读取：
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 else26 {27 std::cerr << "文件打开失败" << endl;28 exit(1);29 }30 input.close();31 OutputMaze();32 }
输出迷宫：将墙壁用其他颜色标记
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 else14 {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 }
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 else50 {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 }
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 else27 {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_INTENSITY37 | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);38 }
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 maze20 {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
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 else108 {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 else162 {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 else199 {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 else220 {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 else258 {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_INTENSITY268 | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);269 }
welcome.h:
1 #ifndef WELCOME_H2 #define WELCOME_H3 #include <iostream>4 using std::cout;5 using std::endl;6 using std::cin;7 void Welcome(int& n);8 #endif
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 }
测试程序：
堆栈的链式实现见：堆栈的链表方式实现
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 else28 {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 }
输出：此处使用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（迷宫中空闲的位置）
注意这个方法不保证找到的路径是最短路径，从结果也可以看出。
堆栈应用（六）：迷宫搜索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。