迷宫问题是一道经典的回溯算法问题给定一个迷宫矩阵矩阵中的1表示障碍0表示可走通路给定迷宫入口出口要求寻找从入口穿过迷宫到达出口的所有路径有则输出无则给出提示。一本合格的数据结构教科书一般都会介绍迷宫问题网上的分析也是铺天盖地这里就不再赘述重复的内容了。废话不多说简单介绍一下程序然后上代码。该程序用二维数组表示迷宫用另一个二维数组记录迷宫中的位置是否已经走过同时用一个栈存放搜索出的临时路径。程序从迷宫入口开始试探随着回溯试探过程的进行栈的长度不断变化当试探到迷宫出口时栈中存放的就是一条完整的穿过迷宫的路径了输出路径后回溯继续试探下一条路径当回溯到入口时没有新的可走方向时整个回溯试探的过程也就结束了。栈节点中除了存放被路径连接的各单元的行列标外还存放有由该节点代表的单元前往该节点的后继节点代表的单元的方向这么做是为了方便回溯操作的进行。为方便起见程序中迷宫的入口是固定的为左上角单元出口同样固定为右下角单元。这并不妨碍程序的普适性只要稍加修改就可以使程序适用于任意给定的出口和入口的情形。啰嗦了这么半天下面该上代码了代码用C语言编写具体如下。#include iostream #include vector #include string using namespace std; void convert(size_t i, size_t j, unsigned short k); //将当前单元行标列标i,j更新为方向k所指向的相邻单元的行标列标 bool boundary(const size_t i, const size_t j, unsigned short d, const size_t n, const size_t m); //检查(i,j)单元在d方向上是否为迷宫边界,是返回0不是返回1 bool barrier(const size_t m, const size_t n, const vectorvectorbool p); //检查(i,j)单元在d方向上是否遇到障碍是返回0不是返回1 bool visit(const size_t m, const size_t n, const vectorvectorbool t); //检查(i,j)单元在d方向上的相邻单元是否已走过是返回0不是返回1 bool direction(const size_t i, const size_t j, unsigned short d, const size_t n, const size_t m, const vectorvectorbool p, const vectorvectorbool t); //检查(i,j)单元在d方向上是否可走,可走返回1否则返回0 unsigned short trial(const size_t i, const size_t j, unsigned short k, const size_t n, const size_t m, const vectorvectorbool p, const vectorvectorbool t); //在(i,j)单元上从k方向的下一个方向起寻找下一个可走方向,找到返回方向号否则返回0 struct Record //表示路径节点的结构体类型 { size_t x; size_t y; //节点对应单元的行列标 unsigned short mark; //记录当前节点的后继节点对应的单元相对于当前节点对应的单元的方向 Record(size_t x, size_t y, unsigned short m) :x(x), y(y), mark(m) {} }; void outputPath(const vectorRecord path_stack, const size_t end_x, const size_t end_y) { for (const auto run : path_stack) cout ( run.x 1 , run.y 1 )-; cout ( end_x , end_y ) endl; } int main() { size_t i, j; unsigned short k; //i,j为单元位置标识,k为方向参数 size_t m, n; //m为迷宫行数,n为迷宫列数 size_t Num; //flag标志是否存在走出迷宫的路径,Num为找到的路径序号 size_t min 0, max 0; string q; cout please input the number of row and col of the Maze matrix endl; cout please enter the row endl; cout row; cin m; //输入迷宫矩阵行列数 cout please enter the col endl; cout col; cin n; vectorvectorbool p(m, vectorbool(n)); //p指向表示迷宫的二维数组,t指向记录迷宫中的每个位置是否已走过的二维数组 vectorvectorbool t(m, vectorbool(n, false)); //初始化标志迷宫矩阵每一位置是否已走过的矩阵 for (i 0; i m; i) { cout please input the i 1 nd row of Maze matrix endl; //初始化迷宫矩阵,0表示可走,1表示障碍 cin q; for (j 0; j n; j) p[i][j] static_castbool (q[j] - 48); } vectorRecord path_stack; vectorvectorRecord min_path; vectorvectorRecord max_path; Num 0; i 0; j 0; //初始化当前单元行列标,将迷宫左上角单元作为出发点 k 0; //方向参数初始化为0,对左上角单元从头开始试探可走方向 while (true) { unsigned short temp; if ((temp trial(i, j, k, n, m, p, t)) 0) //回溯试探开始 { if (i 0 j 0) //在起始点已无方向可走,回溯结束 break; if (k ! 0) //在(i,j)元上沿k方向后的所有方向均不可走,回溯 { t[i][j] false; path_stack.pop_back(); //(i,j)元节点弹出栈 } } else { if (k 0) //从头开始为(i,j)元找到了可走方向trial(i, j, k, n, m, p, t) { path_stack.push_back(Record(i, j, temp)); //(i,j)元作为节点压入栈 t[i][j] true; //(i,j)元标志为已走 } else //从k方向的下一方向开始为(i,j)元找到了可走方向trial(i, j, k, n, m, p, t) path_stack.back().mark temp; //相应更新(i,j)元节点中的方向 convert(i, j, temp); //沿找到的方向从(i,j)元递进至下一单元 k 0; //为为下一单元从头开始寻找新方向作准备 if (i m - 1 j n - 1) //抵达迷宫出口 { Num; //找到路径数增1 cout endl The Num nd possible route: endl; //输出路径序号 outputPath(path_stack, m, n); if (min_path.empty()) { min_path.push_back(path_stack); min path_stack.size(); } else { if (path_stack.size() min) { min_path.clear(); min_path.push_back(path_stack); min path_stack.size(); } else if (path_stack.size() min) min_path.push_back(path_stack); } if (max_path.empty()) { max_path.push_back(path_stack); max path_stack.size(); } else { if (path_stack.size() max) { max_path.clear(); max_path.push_back(path_stack); max path_stack.size(); } else if (path_stack.size() max) max_path.push_back(path_stack); } } else continue; } const Record back path_stack.back(); //回溯 i back.x; j back.y; k back.mark; } if (min_path.empty()) cout There is no possible route endl; else { cout There are Num routes in total endl; cout The length of shortest route is min 1 shortest routes include: endl; for (const auto run : min_path) { outputPath(run, m, n); } cout The length of longest route is max 1 longest routes include: endl; for (const auto run : max_path) { outputPath(run, m, n); } } } void convert(size_t i, size_t j, unsigned short k) { switch (k) { case 1: --i; break; case 2: --i; j; break; case 3: j; break; case 4: i; j; break; case 5: i; break; case 6: i; --j; break; case 7: --j; break; case 8: --i; --j; break; } } bool boundary(const size_t i, const size_t j, unsigned short d, const size_t n, const size_t m) { if (i 0 || i m - 1 || j 0 || j n - 1) { if (i 0 j ! 0) { if (j ! n - 1) { if (m 1) { if (d 8 || d 1 || d 2 || d 6 || d 5 || d 4) return false; } else { if (d 8 || d 1 || d 2) return false; } } else { if (m 1) { if (d 8 || d 1 || d 2 || d 3 || d 4 || d 5 || d 6) return false; } else { if (n 1) { if (d 8 || d 1 || d 2 || d 3 || d 4 || d 6 || d 7) return false; } else { if (d 8 || d 1 || d 2 || d 3 || d 4) return false; } } } } else { if (j n - 1 i ! 0) { if (i ! m - 1) { if (n 1) { if (d 8 || d 2 || d 3 || d 4 || d 6 || d 7) return false; } else { if (d 2 || d 3 || d 4) return false; } } else { if (m 1) { if (d 8 || d 1 || d 2 || d 3 || d 4 || d 5 || d 6) return false; } else { if (n 1) { if (d 8 || d 2 || d 3 || d 4 || d 5 || d 6 || d 7) return false; } else { if (d 2 || d 3 || d 4 || d 5 || d 6) return false; } } } } else { if (i m - 1 j ! n - 1) { if (j ! 0) { if (m 1) { if (d 8 || d 1 || d 2 || d 4 || d 5 || d 6) return false; } else { if (d 4 || d 5 || d 6) return false; } } else { if (m 1) { if (d 8 || d 1 || d 2 || d 4 || d 5 || d 6 || d 7) return false; } else { if (n 1) { if (d 8 || d 2 || d 3 || d 4 || d 5 || d 6 || d 7) return false; } else { if (d 8 || d 4 || d 5 || d 6 || d 7) return false; } } } } else { if (i ! 0) { if (n 1) { if (d 8 || d 2 || d 3 || d 4 || d 6 || d 7) return false; } else { if (d 6 || d 7 || d 8) return false; } } else { if (m 1) { if (d 8 || d 1 || d 2 || d 4 || d 5 || d 6 || d 7) return false; } else { if (n 1) { if (d 8 || d 1 || d 2 || d 3 || d 4 || d 6 || d 7) return false; } else { if (d 8 || d 1 || d 2 || d 6 || d 7) return false; } } } } } } } return true; } bool barrier(const size_t m, const size_t n, const vectorvectorbool p) { if (p[m][n] false) return true; return false; } bool visit(const size_t m, const size_t n, const vectorvectorbool t) { if (t[m][n] false) return true; return false; } bool direction(const size_t i, const size_t j, unsigned short d, const size_t n, const size_t m, const vectorvectorbool p, const vectorvectorbool t) { if (boundary(i, j, d, n, m) false) //(i,j)元在d方向为边界{ return false; //d方向不可走 size_t m2 i, n2 j; convert(m2, n2, d); if (barrier(m2, n2, p) false) //(i,j)元在d方向遇到障碍 return false; //d方向不可走 if (visit(m2, n2, t) false) //(i,j)元在d方向上的相邻单元已经走过 return false; //d方向不可走 return true; //d方向可走 } unsigned short trial(const size_t i, const size_t j, unsigned short k, const size_t n, const size_t m, const vectorvectorbool p, const vectorvectorbool t) { for (k; k 8; k) //从k方向的下一方向开始寻找从(i,j)元可走的方向 { if (direction(i, j, k, n, m, p, t) 1) return k; //找到可走方向将其返回 } return 0; //没有可走方向返回0 }