迷宫问题，是栈的一个经典应用。在今多年的面试题中特别常见。本博主呢，也就研究了一二。

若有一迷宫，如何寻找通路？


解题思路：

迷宫，可将其看成一个二维数组。给定一个入口，需要判断此入口的上下左右是否越界，是否有通路点。若有通路点，将此点前一个通路点记录并将其置为非0（防止访问下一个通路点时再次判断）。继续寻找下一个通路,...以此类推。若查找不到通路点，则需要回溯。判断是否还有其他通路。

回溯呢，就是将从记录的通路点回退。此特征呢，和我们的栈很相似。所以，栈就在此处派上用场喽。

那么如何判断迷宫是否有通路呢？

判断条件：（1）有通路。当行或者列到达边界时即可判断。

（2）无通路。当回溯时，需要从栈中取出元素。当栈为空时即可判断。


假设有如下迷宫。（迷宫中0为通路）入口点（2,0）。


分析：

看到此迷宫，可将其看成二维数组。但是在程序中不可能一个一个输入（若迷宫很大呢）。所以可将其以文件的形式读取。我们看到在此迷宫处，有一个通路点处有两条通路，若先走下面，行到达边界处，则可直接得出有通路。若先右方，最终无通路可走，则需要回溯，在进一步的判断。当回溯到岔路口时，发现下方还有路可走。继续向下走，最终行到达边界处，即有通路。


程序实现：

"Maze.h"

#pragmaonce#define_CRT_SECURE_NO_WARNINGS1#include<iostream>#include<assert.h>#include<stack>#defineN10usingnamespacestd;structPos{int_row;//行int_col;//列};//从文件中读出数据，并以一位数组存放voidGetMaze(int*a,intn){FILE*f=fopen("test.txt","r");assert(f);for(inti=0;i<n;i++){for(intj=0;j<n;){charch=fgetc(f);if(ch=='0'||ch=='1'){a[i*n+j]=ch-'0';j++;}else{continue;}}}}//打印迷宫voidPrintMaze(int*a,intn){for(inti=0;i<n;i++){for(intj=0;j<n;j++){cout<<a[i*n+j]<<"";}cout<<endl;}}//是否有通路boolPathIsAccess(int*a,intn,Posnext){assert(a);if((next._row>=0)&&(next._row<n)&&(next._col>=0)&&(next._col<n)&&(a[next._row*n+next._col]==0)){returntrue;}returnfalse;}boolMazePath(int*a,intn,Pos&entry,stack<Pos>&path){Poscur=entry;path.push(cur);while(!path.empty()){a[cur._row*n+cur._col]=2;//压栈后将其置为2，防止再次访问到if((cur._col==n-1)||(cur._row==n-1))//通路条件，行或列到达边界{returntrue;}//上Posnext=cur;//将上一个通路点保存next._row--;if(PathIsAccess(a,n,next))//是否越界{cur=next;path.push(cur);continue;}//左next=cur;next._col--;if(PathIsAccess(a,n,next)){cur=next;path.push(cur);continue;}//右next=cur;next._col++;if(PathIsAccess(a,n,next)){cur=next;path.push(cur);continue;}//下next=cur;next._row++;if(PathIsAccess(a,n,next)){cur=next;path.push(cur);continue;}cur=path.top();//回溯path.pop();}returnfalse;}voidTest(){inta[N][N]={};GetMaze((int*)a,N);PrintMaze((int*)a,N);stack<Pos>path;Posentry={2,0};boolret=MazePath((int*)a,N,entry,path);cout<<"是否有通路"<<ret<<endl;PrintMaze((int*)a,N);}

测试结果：

（1）先走右方（出现回溯）

（2）先走下方