C++栈和典型迷宫问题( 四 ) _生活百科

输出结果：

文章插图
5. 栈的应用总是在想，如果没有栈，编程将如何进行，可想而知，栈的重要性。函数调用、递归算法……无处不有栈的身影。下面将通过一个典型的案例加深对栈的理解。
5.1 迷宫问题迷宫问题描述：在一个错综复杂的迷宫世界，有一个入口，有一个出口。在入口位置有一只小老鼠，出口位置有一块奶酪。要求通过编码的方式帮助小老鼠在入口到出口之间找到一个可行的路径。
迷宫问题是一类典型问题，解决此类问题的关键思想包括：

试探过程：每到达一个当前位置（第一个当前位置为入口），记录此当前位置四周可尝试的其它位置，然后选择其中一个位置作为当前位置尝试着继续前进。

如下表格，设值为0的单元格为可通行，1为不可通行。值标识为红色的单元格表示当前位置，在继续前进时，记录其左、右、下三个可行位置。并选择右边位置为新的当前位置。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qgFmPTLw-1665378597893)(D:\红泥巴\我的课程体系\（信息奥赛）课程体系\第一阶段：入门级（CSP-J）\第三部分：数据结构\1_第一章节：线性表\教学教案\栈的图片\6.png)]

回溯过程：当在前进时被阻碍后，退到记录表中下一个可行位置再试。重复试探再回溯至到找到出口。

如上图所示后继续选择右行，则发现被阻碍。

文章插图
这时就需要在已经存储的可行位置选择一个，这步操作称为回溯。

文章插图
很明显，每次记录的可尝试位置是在回溯后使用的，符合先进后出的存储理念。栈在迷宫问题中用来存储可试探的位置。
实现流程：

使用二维数组模拟迷宫。在二维数组中用 0 表示可通行，1 表示不可通行。

#include <iostream>#include <stack>#include <vector>//全局声明int nums[10][10];

初始化迷宫。为了简化问题，会把二维数组的第一行和最后一行，第一列和最一列中的所有单元格赋值 1，表示墙面。

如下图，设置入口位置(1,1)、出口位置为(8,8) 。

文章插图
//全局声明int nums[10][10]= {{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,1,1,1,1,1},{1,1,0,1,0,0,1,1,1,1},{1,1,0,1,0,0,0,0,1,1},{1,1,0,0,0,0,1,0,1,1},{1,1,1,1,0,0,1,0,1,1},{1,1,0,0,0,0,1,0,1,1},{1,1,1,1,0,0,1,0,1,1},{1,1,0,0,0,1,1,0,0,1},{1,1,1,1,1,1,1,1,1,1}, };对于二维数组中的任一位置有左、下、右、上 4 个方向，当前位置的坐标与 4个方位的坐标关系如下图所示：

文章插图
这里定义一个方向结构体，用来存储 4 个方位的增量信息，便于计算。
//方向struct Direction{ //x 方向增量 int xOffset; //y 方向增量 int yOffset;};并且创建 Direction类型数组，用于保存 4 个方向的增量信息。
//全局声明Direction dirs[4]={ {0,1},{1,0},{0,-1},{-1,0} };方向信息，为快速找到当前位置周边的坐标提供了便利。为了存储坐标，这里需要一个坐标结构体：
struct Position { //x坐标 int x; //y坐标 int y; //无参构造 Position() { } //有参构造 Position(int x,int y) {this->x=x;this->y=y; } //判断 2 个坐标是不是同一个位置 bool equals(Position pos) {return this->x==pos.x && this->y==pos.y; } //自我显示 void desc() {cout<<"x:"<<x<<"y:"<<y<<endl; }};