我们看下面这个迷宫----方阵（也可以是矩阵）：


迷宫入口是坐标（2，0）位置，出口是（9，3）。我们假定0代表通路，1代表不通。


现在需要找到哪一条路是通路。我们的思想是借助栈，“回溯法”。回溯是什么意思呢？？？先从起点出发，检查它的上下左右是否是通路（即是否有为数字0处）。也就是说为0通了，压栈，将此位置元素变成2，这样做的好处是明确通路路径。然后继续往下走，判断上下左右 。直至我们找到终点（纵坐标在矩阵的最后一行）。


我们来看下我针对迷宫问题实现的代码：

#include<stack>#include<assert.h>#defineN10//该迷宫10*10.structPos//定义一个结构体，该结构体用来表示坐标。{int_row;int_col;Pos(introw,intcol):_row(row),_col(col){}};template<classT>boolSearchMazePath(int*a,intn,Posentry,stack<T>&paths)//寻找迷宫是否有通路。{assert(a);paths.push(entry);while(!paths.empty()){Poscur=paths.top();a[cur._row*n+cur._col]=2;if(cur._row==n-1){returntrue;}//上Postmp=cur;--tmp._row;if(a[tmp._row*n+tmp._col]==0){paths.push(tmp);continue;}//下tmp=cur;++tmp._row;if(a[tmp._row*n+tmp._col]==0){paths.push(tmp);continue;}//左tmp=cur;--tmp._col;if(a[tmp._row*n+tmp._col]==0){paths.push(tmp);continue;}//右tmp=cur;++tmp._col;if(a[tmp._row*n+tmp._col]==0){paths.push(tmp);continue;}paths.pop();//若上下左右都不通，则回溯。}returnfalse;}voidGetMaze(int*a,intn)//读取到迷宫图案{assert(a);FILE*fout=fopen("MazeMap.txt","r");assert(fout);//若文件打开失败，后续工作则无法完成，因此采用assert防御式编程。for(inti=0;i<n;i++){for(intj=0;j<n;j++){while(true){intmen=fgetc(fout);//读取字符if(men=='0'||men=='1')//是0或者1则转换成数字到二维矩阵中存储。{a[i*n+j]=men-'0';break;}}}}}voidPrintMaze(int*a,intn)//将此迷宫打印出来{for(inti=0;i<n;i++){for(intj=0;j<n;j++){cout<<a[i*n+j]<<"";}cout<<endl;}cout<<endl;}voidTest(){inta[N][N]={};Possp(2,0);//入口坐标GetMaze((int*)a,N);PrintMaze((int*)a,N);stack<Pos>paths;SearchMazePath((int*)a,N,sp,paths);//二维数组实际存储是一维数组，将二维数组强制转换为一维数组传参。PrintMaze((int*)a,N);}intmain(){Test();system("pause");return0;}


有时候，针对迷宫问题，我们还需要求多条路径的最优解（最短路径）。那这时候我们可以用压栈，利用栈帧一层一层压栈的特点实现。