在我们学习数据结构的时候都曾经见过迷宫游戏，迷宫游戏的实现其实并不难，但是，我们在实现每一个算法的时候都应该想一想这个问题的每一个解。最近，博主已经开始重温数据结构啦，记得我们以前学习这里的时候，老师会用队列来实现迷宫最优解的寻找，氮素呢，博主就是这么可爱，博主就是想试试用栈来找一下。

在实现之前让我们先来复习一下栈的特点：first in last out

对于栈这种数据结构我们只能在栈顶对其操作，根据实际情况可将其实现成链式或者顺序结构。但是一般情况下我们都会实现成顺序结构，因为栈的特点导致了顺序结构管理方便，并且CPU缓存利用率更高。下面我们来简单的讲解一下迷宫小游戏

为了避免用户操作的不便性，我们选择将迷宫提前写好放在一个叫做"Maze.h"的文件中

*第一行的两个数字是迷宫的行和列

我们解决迷宫寻路问题的基本思想是回溯。回溯是什么意思呢？ 就是说，找不到就回退的思想。今天我们的程序要解决的问题是寻找最优解，所以，迷宫的每一条路我们都要去走一遍，这样，我们才能找到最短的那条路。

我们先来看一下程序是怎么写的（如果喷，请轻点）

#define_CRT_SECURE_NO_WARNINGS1#pragmaonce#include<cassert>#include<iostream>#include<fstream>#include<stack>usingnamespacestd;structPos{size_t_x;size_t_y;Pos(size_tx,size_ty):_x(x),_y(y){}};stack<Pos>min;boolIsValid(int*a,Poscur,size_tR,size_tC){if((a[cur._x*C+cur._y]==0)&&(cur._x<R)&&(cur._y<C))returntrue;elsereturnfalse;}voidPrintMap(int*Map,size_tm,size_tn){for(size_ti=0;i<m;i++){for(size_tj=0;j<n;j++){std::cout<<Map[i*n+j]<<"";}std::cout<<std::endl;}}voidGetMaze(int*a,size_tRow,size_tCol,std::ifstream&fout){size_tch=0;for(size_ti=0;i<Row;i++){for(size_tj=0;j<Col;){ch=fout.get()-'0';if(ch==0||ch==1){a[i*Col+j]=ch;j++;}elsecontinue;}}PrintMap(a,Row,Col);}boolCheck(int*a,Posentry,intR,intC){PosUp=entry;PosDown=entry;PosLeft=entry;PosRight=entry;Down._x++;Right._y++;Up._x--;Left._y--;if(IsValid(a,Down,R,C)||IsValid(a,Up,R,C)||IsValid(a,Left,R,C)||IsValid(a,Right,R,C))returntrue;elsereturnfalse;}boolGamePlay(int*a,Posentry,size_tR,size_tC){assert(a);stack<Pos>s1;Posman=entry;Posnext=man;Poscur=entry;while(1){if(!Check(a,man,R,C)){cout<<"最佳路径长度:";cout<<min.size()<<endl;returntrue;}s1.push(man);while(!s1.empty()){a[man._x*C+man._y]=2;if(man._x==(R-1)||man._y==(C-1)){cout<<"Find&end"<<endl;if((s1.size()<min.size())||min.size()==0)min=s1;while(!s1.empty()){cur=s1.top();s1.pop();if(Check(a,cur,R,C)){man=cur;break;}}if(s1.empty()){cout<<"最佳路径长度:";cout<<min.size()<<endl;returntrue;}}//********************************************下next=man;next._x++;if(IsValid(a,next,R,C)){s1.push(man);man=next;continue;}//********************************************右next=man;next._y++;if(IsValid(a,next,R,C)){s1.push(man);man=next;continue;}//********************************************左next=man;next._y--;if(IsValid(a,next,R,C)){s1.push(man);man=next;continue;}//********************************************上next._x--;if(IsValid(a,next,R,C)){s1.push(man);man=next;continue;}else{man=s1.top();s1.pop();}}man=entry;}}voidGameTest(){//**********************从文件读入迷宫大小**********************ifstreamfout("Maze.txt");stack<int>s1;intRow=0;intCol=0;charch=fout.get();while(ch!=''){inttmp=ch-'0';s1.push(tmp);ch=fout.get();}intc=0;while(!s1.empty()){Row+=s1.top()*(int)pow(10,c);s1.pop();c++;}ch=fout.get();while(ch!=''&&ch!='\n'){inttmp=ch-'0';s1.push(tmp);ch=fout.get();}c=0;while(!s1.empty()){Col+=(int)s1.top()*(int)pow(10,c);s1.pop();c++;}int*a=newint[Row*Col];//********************************************************Posentry(0,1);cout<<endl<<"***********Map**********"<<endl;GetMaze(a,Row,Col,fout);GamePlay(a,entry,Row,Col);cout<<endl<<"***********Map**********"<<endl;PrintMap(a,Row,Col);fout.close();}

**记得在打开文件的时候做异常处理哦。博主在这里就不改了，小伙伴们自己看看

上面的代码呢，其实写的非常的不好，尤其是在代码复用的方面，不过，博主今天只是来举个栗子，今后会更加注意，你们也要注意哦，上面是个反面教材（请理解一个看见自己代码想吐的我）

解法详解：用一个全局的栈结构来存储最优路径 min

用一个局部的站结构来存储当前一次得出的路径 s1

每一步都需要判断上下左右四个方向是否可走

***注意：每次判断时将next的值先赋成当前的位置再进行加减否则产生副作用

两层循环：里面一层即当前一次寻路完成

外面一层即再也无路可循时我们获得了最优解

**嗯，再看一眼仍然觉得这个代码看得我辣眼睛（捂脸）。

请围观群众不吝赐教哦~