C语言学习日记（15）——回溯法解迷宫非递归版

用递归来实现回溯应该是很常见的一种思路。因为回溯法最核心的问题就是如何保存每一步已经选择过的方案信息，以供回退时继续选择下一个方案。而使用递归函数恰好利用了函数调用栈保存了每一步的“进度”，使得每一次函数返回时上一级函数可以继续这个“进度”。

虽然递归实现起来简单易理解，但使用递归并不是唯一的选择，而且，使用递归总给人一种效率可能不高的感觉。通过简单改造，我们也可以使用非递归的方法来实现回溯法。具体思路是：

为了保存每一步的“进度”，可以这样做，用一个int choose[25]数组来充当一个栈，数组每个元素可以从0取到3，分别代表上下左右。当进行到某一步时，按上下左右的顺序进行试探，对应的数组元素就从0开始变大，假设可以向下走一步，此时数组元素的值就变为了1，这样就保存了这一步的“进度”信息，当发生回退时，可以继续从2开始，即从左边继续试探。还要用一个int top来充当栈顶指针，当前进一步top就加1，回退一步top就减1。具体实现代码如下：

#include<stdio.h>
//定义上下左右方向
int direction[4][2] = {-1,0,1,0,0,-1,0,1}; 
int puzzle[5][5] = {
    1,1,1,1,1,
    0,0,1,0,1,
    1,0,0,0,1,
    1,0,0,0,0,
    1,1,1,1,1
};
int path[25][2] = {0};  //用于记录路径
int choose[25] = {0};  //记录每一步已经选择到了哪个方向，0-3分别表示表示上下左右，全部初始为0
int top = 0;   //栈顶指针，总是指向最后一个元素
void getpath(int,int,int,int);
int main()
{
    int startx = 1,starty = 0,endx = 3,endy = 4;   //设置起点，终点坐标
    path[0][0] = startx;
    path[0][1] = starty;                    //将起点加入路径
    getpath(startx,starty,endx,endy);
    return 0;
}
void getpath(int startx,int starty,int endx,int endy)
{
    static int count = 0;      //统计路径条数
    int newx,newy;    //保存新的坐标
    while(top != -1)   //如果回退到入口位置，top=0，再继续回退，则top=-1，此时无路可退，算法结束
    {
        for(;choose[top] < 4;choose[top]++)  //每一步从0（上）开始试探，只要某个方向可行就进入下一步
        {
            newx = path[top][0] + direction[choose[top]][0];
            newy = path[top][1] + direction[choose[top]][1];  //根据当前位置和选择的方向计算新坐标
            if(newx == endx && newy == endy)        //如果到达出口
            {
                count++;                                                //路径总数加1
                printf("\n%d:  ",count);
                for(int j = 0;j <= top;j++)
                printf("(%d,%d) ",path[j][0],path[j][1]);   
                printf("(%d,%d)",endx,endy);                 //打印路径
            }
            if(!(newx >= 0 && newy >= 0 && newx <= 4 && newy <= 4)) continue;  //如果出界，则换个方向试探
            if(puzzle[newx][newy] == 0)  //如果是通道
            {
                puzzle[path[top][0]][path[top][1]] = 1;    //将当前所在位置变成墙，防止走原路
                top++;     //栈指针加1
                path[top][0] = newx;        
                path[top][1] = newy;    //将新的坐标添加到路径
                break;      //此时跳出试探的循环，进入新的一步         
            }
        }
        if(choose[top] > 3)   //如果当前位置四个方向都已经试过，就要回退
        {
            choose[top] = 0;    // 回退前“重置”当前所在位置试探“进度”，这一点很重要
            top--;            //栈顶指针减1，回退一步
            puzzle[path[top][0]][path[top][1]] = 0;    //回退后将当前所在位置变回通道
            choose[top]++;  //换到下一个方向，如果没有这一条，回退后会重复试探之前的方向
        }
    }
}