沦落人闲居

写在前面：私不是程序员，也不是学信科的，也只是最近开始没事的时候翻翻C语言的书。因此阁下很可能会觉得下文所述的想法很原始或是阁下早已用过了。私在此只是记录一下自己的想法。

现阶段私学C语言用的书是宋劲杉的《Linux C编程一站式学习》，里面讲深度优先搜索的时候讲的是个走迷宫问题，用1表示墙，0表示路，从左上走到右下。代码如下：

#include <stdio.h>
#define MAX_ROW 5
#define MAX_COL 5

struct point { int row, col; } stack[512];
int top = 0;

void push(struct point p)
{
    stack[top++] = p;
}

struct point pop(void)
{
    return stack[--top];
}

int is_empty(void)
{
    return top == 0;
}

int maze[MAX_ROW][MAX_COL] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0,
};

void print_maze(void)
{
    int i, j;
    for (i = 0; i < MAX_ROW; i++) {
        for (j = 0; j < MAX_COL; j++)
            printf("%d ", maze[i][j]);
        putchar('n');
    }
    printf("*********n");
}

struct point predecessor[MAX_ROW][MAX_COL] = {
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
};

void visit(int row, int col, struct point pre)
{
    struct point visit_point = { row, col };
    maze[row][col] = 2;
    predecessor[row][col] = pre;
    push(visit_point);
}

int main(void)
{
    struct point p = { 0, 0 };

    maze[p.row][p.col] = 2;
    push(p);

    while (!is_empty()) {
        p = pop();
        if (p.row == MAX_ROW - 1  /* goal */
            && p.col == MAX_COL - 1)
            break;
        if (p.col+1 < MAX_COL     /* right */
            && maze[p.row][p.col+1] == 0)
            visit(p.row, p.col+1, p);
        if (p.row+1 < MAX_ROW     /* down */
            && maze[p.row+1][p.col] == 0)
            visit(p.row+1, p.col, p);
        if (p.col-1 >= 0          /* left */
            && maze[p.row][p.col-1] == 0)
            visit(p.row, p.col-1, p);
        if (p.row-1 >= 0          /* up */
            && maze[p.row-1][p.col] == 0)
            visit(p.row-1, p.col, p);
        print_maze();
    }
    if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
        printf("(%d, %d)n", p.row, p.col);
        while (predecessor[p.row][p.col].row != -1) {
            p = predecessor[p.row][p.col];
            printf("(%d, %d)n", p.row, p.col);
        }
    } else
        printf("No path!n");

    return 0;
}

大概意思就是每次弹出一个栈，找到周围所有的合法步骤然后把它们栈压进栈区，下一轮时再弹出最后压入的栈，如果走入死路就再次弹栈，找另外一条可能路线，直到找到迷宫的解。如果栈空了就说明无路可走，打出“No path !”。
但是找到解之后就比较麻烦。如何输出路径呢？这段代码使用的方法是建立一个predecessor数组，用来表示每个点的前趋，然后从最后一个点顺藤摸瓜往前找，逐渐打印出来。但这个predecessor数组占用的空间很大，且只能从后向前找，不便于找到其中的某个特定步骤。怎么解决这一问题呢？作者宋劲杉出了一道思考题，还问读者能够想出几种方法，可见方法是不止一种的。

在正确理解这段代码之前，私一直认为栈区中至少应该存有正确路径走过的所有的点，后来才明白这个想法是有问题的。由于每个循环开始时栈顶已经弹出了，此时如果再在这一点继续向深处找，新压入的栈就会把刚才弹出的栈顶覆盖掉，这样找到最后整个栈中在极端情况下（例如整个迷宫都没有岔路）可能一个点也不剩。此外一个循环内是4个方向均会搜索，所以如果有岔路，就会压入多个点，但弹出时只会弹出一个点，所以栈中会残留错误道路的点。

怎么修改呢？其实很容易。原来每个循环会从栈顶弹出一个栈，其实找到路径之后，完全可以把这一栈再压回去，比如这样：

int main(void)
{
    struct point p = { 0, 0 };

    maze[p.row][p.col] = 2;
    push(p);

    while (!is_empty()) {
        p = pop();
        if (p.row == MAX_ROW - 1  /* goal */
            && p.col == MAX_COL - 1)
            break;
        if (p.col+1 < MAX_COL     /* right */
            && maze[p.row][p.col+1] == 0) {
            top++;
            visit(p.row, p.col+1, p);
        } else if (p.row+1 < MAX_ROW     /* down */
            && maze[p.row+1][p.col] == 0) {
            top++;
            visit(p.row+1, p.col, p);
        } else if (p.col-1 >= 0          /* left */
            && maze[p.row][p.col-1] == 0) {
            top++;
            visit(p.row, p.col-1, p);
        } else if (p.row-1 >= 0          /* up */
            && maze[p.row-1][p.col] == 0) {
            top++;
            visit(p.row-1, p.col, p);
        }
        print_maze();
    }

    int i;
    if (!is_empty()) {
        for (i=0; i<top; i++)
            printf("(%d, %d)n", stack[i]);
    } else
        printf("No path.n");

    return 0;
}

如果找到了可用的路，由于有了top++，相当于仅仅是读取到栈顶的数据（而栈没有弹出），这样在搜索路径压栈的时候就不会把原来的栈顶覆盖掉，从而保证了栈中存在所有正确路径上的点。解决残留错误道路的点的问题也很容易，只需让一个循环内如果搜索到了一条可以深入的路径就停止（用else实现），否则再搜索下一条路径。如果找到死路栈会逐个弹出，直到岔路口，所以不用担心找不到正解。到最后如果迷宫存在解的话，栈中所保存的就是正确的路径。由于例子中的“栈”是一个数组（当然您可能会反驳说这个例子中stack[]并不是真正意义上的栈，“栈”在理论上应该只能访问顶端的元素，但那只是个形式问题），于是可以很容易地访问任何一步的点，输出的时候正着打反着打跳着打均可，程序中所有和predecessor有关的内容便可以删去了。

但是事实上这个办法在程序效率上是劣化而不是优化，首先虽然不需要predecessor了，但是栈空间消耗变得更大。原本栈空间的消耗和分岔路的多少有关，现在则是和路径的长度有关而与有多少岔路无关。那么栈空间的最小值应该是多大呢？私还没考虑好，但分配为整个迷宫的大小肯定是足够的。还有个问题是原来的方式由于覆盖了之前走过的路径，只保留岔路上其他方向的点，如果找到死路，弹栈后会直接跳到另外一个可能的岔路继续搜索，而修改后的方法如果找到死路，必须沿原路一步步跳回岔路口。再加上top++所用的时间，程序效率比原来要低，而且岔路越多越深入，效率上的差距越明显。

前几天看到个好玩的推，说“情人节我玩一天连连看，消灭一对是一对”。私寻思既然学了DFS和BFS，不如自己也写个文本连连看玩玩？再说吧。

另：为嘛我Tag里写C，wordpress会给自动补全成C++？