复杂迷宫问题的递归实现以及最短路径

复杂迷宫就是有多条通路的迷宫，而且要求解最短路的话就要用递归集合栈，用递归探测，寻找所有通路，用栈保存所走过的路径，具体方法为： （1）从当前点为起点探测由它开始能前进的点（这里的探测方向为上，有，左，下）； （2）找到能前进的点之后，首先将这个点的坐标压入栈（path）中保存起来，并将这个点的值赋为前一个点的值加1；递归调用这个函数，继续探测； （3）当前结点不能前进之后，将path中的点弹出栈，探测它的另一个可以前进的方向； （4）当前结点为出口时，比较栈path和栈shortestpath的size，将值较小的栈赋值给shortestpath;

具体代码如下：

#include <iostream> #include <stack> using namespace std; const int N = 10; int MazeMap[N][N] = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 0, 1, 1, 0, 0, 0, 1, 1 }, { 1, 1, 0, 1, 1, 0, 1, 0, 1, 1 }, { 1, 1, 0, 0, 0, 0, 0, 0, 1, 1 }, { 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 }, { 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 }, { 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 }, }; void PrintMap(int maze[][N], size_t N) { for (size_t i = 0;i < N;++i) { for (size_t j = 0;j < N;++j) { cout << maze[i][j]<<" "; } cout << endl; } } struct Pos { size_t i; size_t j; }; bool IsGoingR(int maze[][N], size_t n, Pos cur, Pos next) { if (next.i < n && next.i >= 0 && next.j < n && next.j >= 0) { if (maze[next.i][next.j] == 0 || maze[cur.i][cur.j] < maze[next.i][next.j]) { return true; } } return false; } bool GetTheWayR(int maze[][N], size_t n, Pos pos, stack<Pos>& path,stack<Pos>& shortestpath) { path.push(pos); if (pos.i == n - 1) { if (path.size() < shortestpath.size()||shortestpath.empty()) { shortestpath = path; } } Pos next; //上 next = pos; next.i = pos.i - 1; if (IsGoingR(maze, N, pos, next)) { maze[next.i][next.j] = maze[pos.i][pos.j] + 1; if (GetTheWayR(maze, N, next, path, shortestpath)) { return true; } } //右 next = pos; next.j = pos.j + 1; if (IsGoingR(maze, N, pos, next)) { maze[next.i][next.j] = maze[pos.i][pos.j] + 1; if (GetTheWayR(maze, N, next, path, shortestpath)) { return true; } } //左 next = pos; next.j = pos.j - 1; if (IsGoingR(maze, N, pos, next)) { maze[next.i][next.j] = maze[pos.i][pos.j] + 1; if (GetTheWayR(maze, N, next, path, shortestpath)) { return true; } } //下 next = pos; next.i = pos.i + 1; if (IsGoingR(maze, N, pos, next)) { maze[next.i][next.j] = maze[pos.i][pos.j] + 1; if (GetTheWayR(maze, N, next, path, shortestpath)) { return true; } } path.pop(); return 0; } void Test() { PrintMap(MazeMap, N); stack<Pos> path; stack<Pos> shortestpath; Pos entry = { 2,0 }; GetTheWayR(MazeMap, N,entry,path,shortestpath); cout << endl; PrintMap(MazeMap, N); }

运行结果： 这里我们可以清楚地看到所走过的路径。

而且我们可以看到，栈shortestpath中保存着最短路径的坐标。