写在前面：私不是程序员，也不是学信科的，也只是最近开始没事的时候翻翻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++？