我们知道栈的特点是：后进先出（First In Last Out）;也就是说只能在栈的尾部进

行压栈和出栈，而且出栈的时候只能从最后一个数据开始。

所以我们利用栈这个特点，来实现这个迷宫。在这之中我们要采用“回溯”的方法去处理当遇到路径不通的情况。

原理：每找到一个通路，就将这个数据压栈，这样当前位置的上一个位置就位于栈的顶部，假如当前位置的上下左右都找不到通路的时候，就开始回溯，也就是开始从来的路往回走，而之前走过的路都存在栈里面，所以只需要一个一个的Pop就能依次往回退，每退一次，就寻找上下左右有没有通路，如果找到通路就继续往下走，并压栈，直到走出整个迷宫。

#define_CRT_SECURE_NO_WARNINGS1#include"MazeMap.h"#include<stdio.h>voidtest(){inta[N][N];GetMaze((int*)a,N);stack<pos>paths;posentry={2,0};cout<<searchpath((int*)a,10,entry,paths)<<endl;display((int*)a,N);}intmain(){test();system("pause");return0;}

#pragmaonce#include<stack>#include<assert.h>#defineN10#include<iostream>usingnamespacestd;structpos{int_row;int_col;};voidGetMaze(int*a,intn){assert(a);FILE*fout=fopen("C:\\maze.txt","r");assert(fout);for(inti=0;i<n;i++){for(intj=0;j<n;){charch=fgetc(fout);if(ch=='1'||ch=='0')//只读有效的字符，遇空格不转换{a[i*n+j]=ch-'0';j++;}else{continue;}}}fclose(fout);}boolCheckisAccess(int*a,intn,constpos&next)//检查当前的路径是否通行{introw=next._row;intcol=next._col;if(row>=0&&row<n&&col>=0&&col<n&&a[next._row*n+next._col]==0){returntrue;}else{returnfalse;}}boolsearchpath(int*a,intn,posentry,stack<pos>&paths){assert(a);paths.push(entry);//将入口地址（坐标）push到栈中while(!paths.empty())//如果栈为空，就没找到出口{poscur=paths.top();a[cur._row*n+cur._col]=2;//将走过的路径置为2if(cur._row==n-1){returntrue;}posnext=cur;//先将cur赋给next为了下面如果next改变后不满足，next._row--;//上if(CheckisAccess(a,n,next)){cur=next;paths.push(cur);continue;}next=cur;next._col++;//右if(CheckisAccess(a,n,next)){cur=next;paths.push(cur);continue;}next=cur;next._row++;//下if(CheckisAccess(a,n,next)){cur=next;paths.push(cur);continue;}next=cur;next._col--;//左if(CheckisAccess(a,n,next)){cur=next;paths.push(cur);continue;}next=cur;paths.pop();//如果遇到不通（在此即四个方向都不为0）然后，让栈中保存}的坐标pop（即往回倒）重复试探四个方向直到找到另一returnfalse;条可通路径；}voiddisplay(int*a,intn)//打印{for(inti=0;i<n;i++){for(intj=0;j<n;j++){cout<<a[i*n+j]<<"";}cout<<endl;}}

至此，一个简单的迷宫就完成了，以上左边的图就是开始的迷宫。右边的图是结果。最终，每次走过的地方都被标志成2.