下面简单阐述下使用栈（循环）和使用递归来走迷宫的区别：
使用递归： 分为两个部分： 一部分为已走过的路径（通路） 另一问题是：递归的子问题（根据下一个可以通的位置继续查找出口）。 将走过的路径保存在栈帧内。 递归结束时返回上一层栈帧，销毁当前栈帧。
使用栈（保存走过的路径） 分为两个部分： 一部分为已走过的路径（通路），将其保存在栈内 另一部分为： 试探四个方向，沿着某个可以走通的方向一直试探下去，直到走不通时，退出栈顶元素，栈顶元素始终为当前所处的位置。
1.递归走迷宫： （利用回溯法）
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> using namespace std; #include<cassert> struct Pos//设置坐标 { Pos(int x, int y) :_x(x) , _y(y) {} int _x; int _y; }; template<size_t M,size_t N> class Maze { public: Maze(int **arr, FILE* fp)//构造迷宫 :_row(M) , _col(N) , _maze(arr) { int ch = 0; assert(fp); for (size_t i = 0; i < _row; ++i)//从文件中读取迷宫 { for (size_t j = 0; j < _col;) { char ch = fgetc(fp); if (ch == '0' || ch == '1') { _maze[i][j] = ch - '0'; ++j; } } } fclose(fp); } bool PassMaze(Pos Entry) { //递归算法 Pos cur = Entry; Pos next = cur; _maze[next._x][next._y] = 2;//将走过的路进行标记 //判断是否为出口 if (next._x == N - 1) { return true; } //向上查探 next._x -= 1; if (_CheckAccess(next)) { if (PassMaze(next)) { return true; } } //向右查探 next = cur; next._y += 1; if (_CheckAccess(next)) { if (PassMaze(next)) { return true; } } //向下查探 next = cur; next._x += 1; if (_CheckAccess(next)) { if (PassMaze(next)) { return true; } } //向左查探 next = cur; next._y -= 1; if (_CheckAccess(next)) { if (PassMaze(next)) { return true; } } //走到死胡同时标记为3 _maze[cur._x][cur._y] = 3; return false; } ~Maze() { for (int i = 0; i <_row; ++i) { delete[] _maze[i]; } delete[] _maze; } friend ostream& operator<<(ostream& out, Maze& m); protected: bool _CheckAccess(Pos cur) { if (cur._x >= 0 && cur._x < N && cur._y >= 0 && cur._y < N && _maze[cur._x][cur._y] == 1) { return true; } return false; } private: int** _maze; int _row; int _col; }; ostream& operator<<(ostream& out, Maze<10,10>& m) { for (int i = 0; i < m._row; ++i) { for (int j = 0; j < m._col; ++j) { out << m._maze[i][j] << " "; } cout << endl; } return out; }测试代码：
void Test() { FILE* fp = fopen("Maze.txt", "r"); int row = 0; int col = 0; fscanf(fp, "%d %d", &row, &col); int Start_x = 0; int Start_y = 0; fscanf(fp, "%d %d", &Start_x, &Start_y); //动态开辟二维数组 int **arr = new int*[row]; for (int i = 0; i < col; ++i) { arr[i] = new int[col]; } Maze<10,10> maze(arr,fp);//初始化迷宫 cout << maze << endl; cout << maze.PassMaze(Pos(Start_x, Start_y)) << endl; cout << maze << endl; fclose(fp); } int main() { Test(); return 0; }2.非递归走迷宫（利用栈来保存迷宫的路径）
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> using namespace std; #include<cassert> #include<stack> struct Pos//设置坐标 { Pos(int x, int y) :_x(x) , _y(y) {} int _x; int _y; }; template<size_t M,size_t N> class Maze { public: Maze(int **arr, FILE* fp)//构造迷宫 :_row(M) , _col(N) , _maze(arr) { int ch = 0; assert(fp); for (size_t i = 0; i < _row; ++i)//从文件中读取迷宫 { for (size_t j = 0; j < _col;) { char ch = fgetc(fp); if (ch == '0' || ch == '1') { _maze[i][j] = ch - '0'; ++j; } } } fclose(fp); } //使用循环 bool PassMaze(Pos Entry) { stack<Pos > s; s.push(Entry); _maze[Entry._x][Entry._y] = 2; while (!s.empty()) { Pos cur = s.top(); _maze[cur._x][cur._y] = 2; if (cur._x == N - 1) { return true; } //向上查探 Pos next = cur; next._x -= 1; if (_CheckAccess(next)) { s.push(next); continue; } //向右查探 next = cur; next._y += 1; if (_CheckAccess(next)) { s.push(next); continue; } //向下查探 next = cur; next._x += 1; if (_CheckAccess(next)) { s.push(next); continue; } //向左查探 next = cur; next._y -= 1; if (_CheckAccess(next)) { s.push(next); continue; } s.pop(); _maze[cur._x][cur._y] = 3; } return false; } ~Maze() { for (int i = 0; i <_row; ++i) { delete[] _maze[i]; } delete[] _maze; } friend ostream& operator<<(ostream& out, Maze& m); protected: bool _CheckAccess(Pos cur) { if (cur._x >= 0 && cur._x < N && cur._y >= 0 && cur._y < N && _maze[cur._x][cur._y] == 1) { return true; } return false; } private: int** _maze; int _row; int _col; }; ostream& operator<<(ostream& out, Maze<10,10>& m) { for (int i = 0; i < m._row; ++i) { for (int j = 0; j < m._col; ++j) { out << m._maze[i][j] << " "; } cout << endl; } return out; }测试代码如下：
void Test() { FILE* fp = fopen("Maze.txt", "r"); int row = 0; int col = 0; fscanf(fp, "%d %d", &row, &col); int Start_x = 0; int Start_y = 0; fscanf(fp, "%d %d", &Start_x, &Start_y); //动态开辟二维数组 int **arr = new int*[row]; for (int i = 0; i < col; ++i) { arr[i] = new int[col]; } Maze<10,10> maze(arr,fp);//初始化迷宫 cout << maze << endl; cout << maze.PassMaze(Pos(Start_x, Start_y)) << endl; cout << maze << endl; fclose(fp); } int main() { Test(); return 0; }迷宫中有多条路径时，查找最短路径：
第一种方法：(有缺陷)
先走一条路，走到出口时不返回而是将出口封住，从而利用回溯查找第二条路，这种方法只有在特定情况下（当每条路径的出口都不相同时）才会成功，而当遇到下面的情况（有多条路径是一个出口时），就有可能找不到最优路径。
迷宫（0代表墙，1代表通路，2代表入口）：
0020000000 0011100000 0000100000 1000100000 0000011110 0011100000 0010000000 0011000000 0001111000 0000001000方法二、（有缺陷）
利用递归，当找到一条路时，并不进行返回，即就是获取迷宫路径的函数没有返回值， 当找到一条路径时，会进行回溯至下一条路径，直到最终走完迷宫中所有的通路。
这里需要借助两个栈，一个path栈保存每次走的路径，另一个shortpath保存最短路径。
缺陷：标记方式的问题：走过的通路标记为2，而不通的路标记为3. 那么走过的路径就不会再走，那么当有几条路径的出口相同时，查找的最优解就可能不是我们想要的结果。
方法三、(最终可以适用任何场景)
和上述方式大致相同，只是改变了标记方式：使得走过的路径还可以再走。 将入口设置为2，每走一步将此位置的值设置为上个位置值加1. 利用某种条件，就可以找到所有的路径。
求迷宫的最优解需要注意的问题是： 1.必须保证所有的路径都可以走一遍；（使用递归，找到一条路径并不返回） 2.必须保证走过的路径还可以再走（该标记方式）
代码如下：
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> using namespace std; #include<cassert> #include<stack> struct Pos//设置坐标 { Pos(int x, int y) :_x(x) , _y(y) {} int _x; int _y; }; template<size_t M,size_t N> class Maze { public: Maze(int **arr, FILE* fp)//构造迷宫 :_row(M) , _col(N) , _maze(arr) { int ch = 0; assert(fp); for (size_t i = 0; i < _row; ++i)//从文件中读取迷宫 { for (size_t j = 0; j < _col;) { char ch = fgetc(fp); if (ch == '0' || ch == '1' || ch == '2') { _maze[i][j] = ch - '0'; ++j; } } } fclose(fp); } //递归算法走迷宫 bool PassMaze(Pos Entry) { Pos cur = Entry; Pos next = cur; _maze[next._x][next._y] = 2;//将走过的路进行标记 //判断是否为出口 if (next._x == N - 1) { return true; } //向上查探 next._x -= 1; if (_CheckAccess(next)) { if (PassMaze(next)) { return true; } } //向右查探 next = cur; next._y += 1; if (_CheckAccess(next)) { if (PassMaze(next)) { return true; } } //向下查探 next = cur; next._x += 1; if (_CheckAccess(next)) { if (PassMaze(next)) { return true; } } //向左查探 next = cur; next._y -= 1; if (_CheckAccess(next)) { if (PassMaze(next)) { return true; } } //走到死胡同时标记为3 _maze[cur._x][cur._y] = 3; return false; } //获取迷宫的最优解 void GetShortPath(Pos Entry, stack<Pos>& path, stack<Pos>& shortPath) { //递归算法 Pos cur = Entry; Pos next = cur; path.push(cur); //_maze[next._x][next._y] = 2;//将走过的路进行标记 //判断是否为出口 if (next._x == N - 1) { Print(); if (shortPath.empty() || path.size() < shortPath.size()) { shortPath = path; } } //向上查探 next._x -= 1; if (_CheckAccess(next, cur)) { _maze[next._x][next._y] = _maze[cur._x][cur._y] + 1; GetShortPath(next, path, shortPath); } //向右查探 next = cur; next._y += 1; if (_CheckAccess(next, cur)) { _maze[next._x][next._y] = _maze[cur._x][cur._y] + 1; GetShortPath(next, path, shortPath); } //向下查探 next = cur; next._x += 1; if (_CheckAccess(next,cur)) { _maze[next._x][next._y] = _maze[cur._x][cur._y] + 1; GetShortPath(next, path, shortPath); } //向左查探 next = cur; next._y -= 1; if (_CheckAccess(next,cur)) { _maze[next._x][next._y] = _maze[cur._x][cur._y] + 1; GetShortPath(next, path, shortPath); } path.pop(); } ~Maze() { for (int i = 0; i <_row; ++i) { delete[] _maze[i]; } delete[] _maze; } //friend ostream& operator<<(ostream& out, Maze& m); void Print() { if (_maze) { for (size_t i = 0; i < N; ++i) { for (size_t j = 0; j < N; ++j) { cout << _maze[i][j] << " "; } cout << endl; } cout << endl; } } protected: bool _CheckAccess(Pos cur) { if (cur._x >= 0 && cur._x < N && cur._y >= 0 && cur._y < N && _maze[cur._x][cur._y] == 1) { return true; } return false; } bool _CheckAccess(Pos& next,Pos& cur) { if (next._x >= 0 && next._x < N && next._y >= 0 && next._y < N ) { if (_maze[next._x][next._y] == 1) { return true; } else if (_maze[next._x][next._y] == 0) { return false; } else { if (_maze[cur._x][cur._y] + 1 < _maze[next._x][next._y]) { return true; } } } return false; } private: int** _maze; int _row; int _col; }; void Test() { FILE* fp = fopen("Maze.txt", "r"); int row = 0; int col = 0; fscanf(fp, "%d %d", &row, &col); int Start_x = 0; int Start_y = 0; fscanf(fp, "%d %d", &Start_x, &Start_y); //动态开辟二维数组 int **arr = new int*[row]; for (int i = 0; i < col; ++i) { arr[i] = new int[col]; } Maze<10,10> maze(arr,fp);//初始化迷宫 maze.Print(); //cout << maze << endl; stack<Pos > path, shortPath; maze.GetShortPath(Pos(Start_x, Start_y),path,shortPath); //maze.Print(); fclose(fp); } int main() { Test(); return 0; }结果显示（打印的太难看，表示一下意思就好，笑脸）：
