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

创建栈。

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

这里使用 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;}执行结果：