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

#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; }};

创建栈。

用来存储当前位置周边所有可以通行的位置。

这里使用 STL提供的stack容器。别忘记包含<stack>头文件。

//全局声明stack<Position> myStack;

核心搜索算法。

所有核心代码直接编写在 main 函数中，下面代码中使用到了 vector，存储已经搜索到的位置。还有一点要注意，当某个位置被压入栈中后，要标识为被压入，这里把此位置值设置为 -1 。
int main(int argc, char** argv) { //起点位置 Position startPos(1,1); //终点位置 Position endPos(8,8); //保存走过的位置 vector<Position> paths; //向栈中压入起始位置 mazeStack.push(startPos); //设置起始位置为已经访问过 maze[startPos.x][startPos.y]=-1; //临时存储栈顶位置 Position tmp; while(!mazeStack.empty()) {//取出栈顶位置tmp=mazeStack.top();//删除栈顶数据mazeStack.pop(); //当前搜索位置存储在 vector 中paths.push_back(tmp);//判断是否已经到了终点if (tmp.equals(endPos)) {//到达终点，结束break;} else {for(int i=0; i<4; i++) {//查找当前位置 4 个方向有无可通行位置,并压入栈中Position nextPos(tmp.x+dirs[i].xOffset,tmp.y+dirs[i].yOffset);if(maze[nextPos.x][nextPos.y]==0) {mazeStack.push(nextPos); //标识为已经被压入，避免重复压入maze[nextPos.x][nextPos.y]=-1;}}} } //显示搜索路径 for(int i=0;i<paths.size();i++){tmp=paths[i];tmp.desc(); } return 0;}执行结果：