本次我们探讨一下迷宫小游戏。

让我们来探讨一下怎样可以得到一条通路，采用栈来实现。

当是通路的时候，节点压栈。当走到尽头不通时，出栈，寻找交叉口，寻找通路。

像这样在第一行存放迷宫的规格（在这里为传参少，定义正方形迷宫），设计迷宫，将迷宫以.txt格式存放在目录下（可以是任何地方，下文以默认路径为例）。

假设入口为(2,0)，出口为迷宫最后一行任意位置。

MAZE.h

#pragmaonce#define_CRT_SECURE_NO_WARNINGS1#include<iostream>usingnamespacestd;#include<assert.h>#include<stack>classPos//迷宫每一点的坐标{public:Pos(introw,intcol):_row(row),_col(col){}int_row;int_col;};voidPrintPos(Pos&pos)//打印节点坐标{cout<<"("<<pos._row<<","<<pos._col<<")";}int*GetMaze(int&N)//从文件中打开迷宫{FILE*font=fopen("maze.txt","r");assert(font!=NULL);//打不开迷宫文件无意义charch;while((ch=fgetc(font))!='\n'){N=N*10+ch-'0';}int*a=newint[N*N];for(inti=0;i<N*N,(ch=fgetc(font))!=EOF;){if(ch=='1'||ch=='0'){a[i]=ch-'0';i++;}}returna;}voidPrintMaze(int*a,constintN)//打印迷宫{cout<<"\n迷宫地图('0'为路,'1'为墙)"<<endl;for(inti=0;i<N;i++){for(intj=0;j<N;j++){cout<<a[i*10+j]<<"";}cout<<endl;}}boolIsOverScope(Pospos,constintN)//判断是否越界{if(pos._col<0||pos._col>=N||pos._row<0||pos._row>=N){returntrue;}returnfalse;}boolIsEndPoint(Pospos,constintN)//判断是否为终点：设迷宫终点为能到达迷宫N-1行{if(pos._col>=0&&pos._col<N&&pos._row==N-1){returntrue;}returnfalse;}boolSearchMazePath(int*a,constintN,Posenrty,stack<Pos>&paths)//寻找通路{//若某一位置节点为0，进行压栈，且将数据改为2，寻找此节点上下左右位置为0的节点，再进行压栈，//若某一位置上下左右没有为0的节点，就出栈寻找上一个节点上下左右为0的节点进行压栈assert(a);Postop=paths.top();a[top._row*N+top._col]=2;while(!IsOverScope(paths.top(),N))//每次都要判断坐标是否越界、还要考虑出口旁边也是出口的情况就会多走几次{//判断是否到达出口if(IsEndPoint(top,N)){returntrue;}if(0==a[(top._row-1)*N+top._col])//上{a[(top._row-1)*N+top._col]=2;Postmp(top._row-1,top._col);paths.push(tmp);top=paths.top();continue;}if(0==a[top._row*N+top._col+1])//右{a[top._row*N+top._col+1]=2;Postmp(top._row,top._col+1);paths.push(tmp);top=paths.top();continue;}if(0==a[(top._row+1)*N+top._col])//下{a[(top._row+1)*N+top._col]=2;Postmp(top._row+1,top._col);paths.push(tmp);top=paths.top();continue;}if(0==a[top._row*N+top._col-1])//左{a[top._row*N+top._col-1]=2;Postmp(top._row,top._col-1);paths.push(tmp);top=paths.top();continue;}//if(0==a[top._row*N+top._col+1]&&top._col+1<N)//右//{//a[top._row*N+top._col+1]=2;//Postmp(top._row,top._col+1);//paths.push(tmp);//top=paths.top();//continue;//}//回退if(a[top._row*N+top._col]==2&&!paths.empty()){paths.pop();if(!paths.empty()){top=paths.top();continue;}else{returnfalse;}}}//if(IsOverScope(top,N)||paths.empty())//从上左右出来returnfalse;}voidPrintPath(stack<Pos>paths)//打印通路{//最少Paths中有一个元素enrty在最底层assert(!paths.empty());cout<<"通路："<<endl;;while(!paths.empty()){PrintPos(paths.top());paths.pop();}cout<<endl;}

test.cpp

#include"MAZE.h"voidtest(){//假设迷宫为N*N型正方形intN=0;int*a=GetMaze(N);PrintMaze(a,N);Posenrty(2,0);stack<Pos>paths;paths.push(enrty);if(SearchMazePath((int*)a,N,enrty,paths)){PrintMaze(a,N);PrintPath(paths);}else{PrintMaze(a,N);cout<<"Thereisnotapathinthismaze!"<<endl;}}intmain(){test();system("pause");return0;}

让我们来看看运行结果。

再试试将最后一行的‘0’改为1，让它变成无通路的迷宫

我们可以在思考一下：

当有好几条通路的时候，我们可以得到最短路吗？

我们可以得到以下思路：

记录最小路的步数 ,到达出口时将出口变为1 ,寻找下一条出口,然后更新最短路.

若要寻找这条最短路，那就可以在寻找一次，当通路的步数与最短路步数一致时输出通路。

但是上述方法存在很大的问题：虽然可以得到一个结果，但是不能够保证就是最短的。

因为，当按照上述编程寻找通路的逻辑 “上右下左” 顺序寻找通路时，就可能会把另一条更短的通路堵住，从而影响最短路的结果。

那到底怎么做呢？ 期待下一篇博客。