求迷宫从入口到出口的所有路径是一个经典的程序设计问题。一般的设计思想就是从入口出发，顺着某个方向向下探索，探索分为上下左右四个方位，哪个方向是通的就将向下走，如果每个方向都走不下去就进行原路“回退”。所以需要一个后进先出的结构来保存从入口到出口的路径。所以运用栈来实现是非常方便的，沿着某个方向走，将每个可通的位置进行入栈标记，再切换到下个位置；如果都不通，则栈顶出栈取消标记，再寻找。下来呢就实现一个简单的迷宫求解问题（求解出一条通路就好），至于求解多条通路并且求出最短路径的问题呢我还在进一步的学习中。

在给出代码之前先来看一下如何动态开辟一个二维数组？

int*a=newint[N*N];int**a=newint*[N];//a[i][j]等价于a[i*N+j];

好了，现在来看迷宫的具体实现：

#define_CRT_SECURE_NO_WARNING#pragmaonce#include<iostream>#include<stack>#include<assert>usingnamespacestd;#defineN10structPos{Pos(size_trow,size_tcol):_row(row),_col(col){}int_row;int_col;};voidGetMaze(int*a,intn)//读入文件{FILE*fout=fopen("MazeMap.txt","r");assert(fout);for(inti=0;i<n;i++){for(intj=0;j<n;){charch=fgetc(fout);if('0'==ch||'1'==ch){a[i*n+j]=ch-'0';j++;}else{continue;}}}fclose(fout);}voidPrintMaze(int*a,intn){for(inti=0;i<n;i++){for(intj=0;j<n;j++){cout<<a[i*n+j]<<"";}cout<<endl;}}boolCheckIsAccess(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;}else{returnfalse;}}boolMazePath(int*a,intn,constPos&entry,stack<Pos>&path){Poscur=entry;//入口位置path.push(cur);while(!path.empty()){//是否已经到出口if(cur._row==n-1){a[cur._row*n+cur._col]=2;returntrue;}a[cur._row*n+cur._col]=2;//*****************************************上Posnext=cur;next._row--;if(CheckIsAccess(a,n,next)){cur=next;path.push(cur);continue;}//*****************************************下next=cur;next._row++;if(CheckIsAccess(a,n,next)){cur=next;path.push(cur);continue;}//*****************************************左next=cur;//左next._col--;if(CheckIsAccess(a,n,next)){cur=next;path.push(cur);continue;}//*****************************************右next=cur;next._col++;if(CheckIsAccess(a,n,next)){cur=next;path.push(cur);continue;}cur=path.top();//到这说明没有通路，所以栈顶出栈path.pop();}returnfalse;}voidTestMaze(){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);}

当迷宫有多个出口时，利用全局栈可以求得最短路径。这个我们下次再议