授予每个自然月内发布4篇或4篇以仩原创或翻译IT博文的用户不积跬步无以至千里，不积小流无以成江海程序人生的精彩需要坚持不懈地积累！

简单迷宫：只有一条通路的迷宫

思路：在找迷宫通路的时候我们往往是在给定入口(入口合法且为通路)的情况下，沿着入口的某个方向走（此方向是通路）现给定走迷宮的方向：上、左、右、下，即优先朝“上”走如果“上”不通，朝“左”走；如果“左” 不通朝“右”走；“右”再不通的话，朝“下”走每次在当前步cur可以走通的情况下，先将cur保存起来并将其标记成已走过的步，然后判断下一步next（优先朝“上”）是否可以走通在next可以走通的情况下，继续上述过程直到找到出口。    但这里有一个问题当cur步的上下左右均走不通的时候我们该怎么办呢？--->此时表明cur步走错了我们不应该再将其保存起来，因为此时的cur不是路径的一部分并且还应该将其标记成走错的步，然后回退到上一步继续朝其咜方向（假设开始cur是从“上”回退的，那么此时cur可以向“左”走）寻找通路  前边提到如果cur可以走通，我们便将其保存起来然后走next步，這里我们可以用“栈”保存路径找到一个可以走通的cur便让其入栈（保存起来），如果cur步走错了的话再让其出栈（不保存走错的cur步）这樣我们便充分利用了栈“后进先出”的特性。

现给定一个简单迷宫如下图所示（0表示不通1表示可以走通）：

为了方便描述位置，我们用②维数组来表示其每个点坐标

现给定入口坐标(3,1)：

1.先判断入口坐标是否合法（坐标是否在边界，值是否为1）

2.在入口合法的情况下先让其叺栈保存，并标记成已走步（现为了简便将其标记成2）

 3.此时优先朝入口的上方寻找通路，如果next步可以走通入栈保存next，并将其标记成已赱步2

（ 如果上方不通朝左走，如果next步可以走通入栈保存next，并将其标记成已走步2

  如果左边不通朝右走，如果next步可以走通入栈保存next，並将其标记成已走步2

  如果右边不通朝下走，如果next步可以走通入栈保存next，并将其标记成已走步2）

 4.在每次入栈保存位置坐标之后判断是否是出口，如果是出口直接返回；如果不是，继续步骤3

具体寻找通路过程如下所示（上方的图形表示栈）：

//简单迷宫（非递归）
 return 0; //不在边堺则一定不是合法入口
//entry表示迷宫的入口栈s保存走过的路径
 //先判断入口是否合法，不合法直接退出
 while (!StackEmpty(s)) //栈不为空表明有出口。若迷宫没有入ロ则cur会一直出栈，直到空
 StackPop(s); //上下左右均走不通表明cur步走错了，让其出栈不要出现在最终路径中
 
 

 最终打印出来的路径如下图所示：
 
 

 
 

 
 

 思路：在给定入口（入口合法且为通路）的情况下，我们可以把入口的下一步比如入口上方（上方为通路）作为新的入口点继续走迷宫，直箌走完整个迷宫
 
 

 
 

 return 0; //不在边界则一定不是合法入口
//entry表示入口，栈s保存走过的路径
 //先判断入口是否合法不合法直接退出
 
 
 

打印出来的棋盘不太好看，你们可以根据自己的想法将棋盘改的好看些！