走迷宫是一种经典的智力游戏，相信很多人都玩过。我们走迷宫的过程一般是这样的：从入口开始尝试，如果走到某个位置有几种方案可以选择，则选择其中的一种方案进行尝试，不断重复这个过程。如果走不通，就回退到前一个位置选择下一个方案尝试，直到找到出口。这种方法叫做回溯法。利用计算机走迷宫的原理和人类走迷宫的原理是类似的。

下面是一个简单的迷宫，深色方块代表墙，白色方块表示通道，入口和出口如图所示。

回溯法走迷宫的基本原理是这样的：

1.将迷宫看成一个二维数组，用1表示墙，用0表示通道。上面的迷宫在计算机眼里看起来是这样的：

 2.将上面二维数组的下标作为每个格子的坐标，方便表示路径。

 3.回溯法的关键问题是如何知道每一步已经做过哪些选择，如果发生回退的话接下来应该选择什么方案？这个问题的一种解决方案是递归，我们可以利用递归调用栈来保存每一步接下来应该选择的方向。定义函数 void getpath(int startx,int starty,int endx,int endy)，表示寻找从（startx，starty）到（endx，endy）的所有路径。函数的基本思想如下：

//以下函数寻找从（startx，starty）到（endx，endy）的所有路径
void getpath(int startx,int starty,int endx,int endy)｛
    设置路径总数 = 0；
    设置步数 = 0；
    for 方向 in [上，下，左，右]｛
        根据选择的方向计算出新的坐标（newx,newy）；
        如果是终点，则路径总数加1，打印路径；
        如果超出边界，选择下一个方向试探；
        如果是通道｛
            检查路径中是否已经存在该点坐标：
                若存在，则路径重复，选择下一个方向试探；
                若不存在，则步数加1，将新的坐标加入到路径上；
                从当前位置递归调用getpath；
                步数减1；
        ｝
    ｝
｝

光看这段描述可能难以把握算法的原理，我们通过在迷宫上具体推理一遍来掌握算法的思想。为此，我将迷宫的通道全都标上字母。看看算法是怎样走迷宫的。

图中A为起点，J为终点。下面我们模拟一下，红色表示当前路径。

 

下面根据上面的图说明一下回溯法的过程，我们在每个位置都是按照上下左右的顺序进行试探：

（1）开始时位于A处，此时路径中只有A，路径总数=0，步数=0。

（2）在A点按上下左右的顺序试探，发现上下都是墙，往左会出界，只能往右走到B。检查发现B点不在路径中，于是将步数加1，将B点加入路径。此时路径为A→B，路径总数=0，步数=1。

（3）在B点按上下左右的顺序试探，发现往上是墙，可以往下走到D，检查发现D点不在路径中，于是将步数加1，将D点加入路径。此时路径为A→B→D，路径总数=0，步数=2。

（4）在D点按上下左右的顺序试探，发现往上是B，而B点已在路径中，不可以走，可以往下走到G，于是将步数加1，将G点加入路径。此时路径为A→B→D→G，路径总数=0，步数=3。

（5,6,7）以此类推，路径变为A→B→D→G→H→E→F，路径总数=0，步数=6。

（8）在F点按上下左右的顺序试探，应该是往上走到C，于是将步数加1，将C点加入路径。此时路径为A→B→D→G→H→E→F→C，路径总数=0，步数=7。

（9）在C点按上下左右的顺序试探，发现都走不通。此时，递归函数会返回，于是回到上一个位置F处，并将步数减1，此时路径又变为A→B→D→G→H→E→F，路径总数=0，步数=6。

（10）回到F点后，因为向上已经尝试过，接下来应该往下走到I，于是将步数加1，将I点加入路径。此时路径为A→B→D→G→H→E→F→I，路径总数=0，步数=7。

（11）在I点按上下左右的顺序试探，发现可以往右走到J。而J恰好是终点，于是将路径总数加1，并打印路径。此时，路径总数=1。

当打印完第一条路径后，递归函数一直回退到H时的栈帧，而H的栈帧还保存着H处下一步应该试探的方向，所以会从H处接着往右走到I，然后到J。此时，路径总数=2。

接下来还会回退至D处，继续这个过程，最终将会找出所有路径。

通过分析，证明上述算法是正确的。接下来就可以编写代码啦。