算法研究：堆栈与深度优先搜索（迷宫问题）

算法研究：堆栈与深度优先搜索（迷宫问题）2013-08-20 csdn Simba888888堆栈的访问规则被限制为Push和Pop两种操作，Push（入栈或压栈）向栈顶添加元素，Pop（出栈或弹出）则取出当前栈顶的元素，也就是说，只能访问栈顶元素而不能访问栈中其它元素。

现在我们用堆栈解决一个有意思的问题，定义一个二维数组：

int maze[5][5] = {

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,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。程序如下：（参考《Linux c 编程一站式学习》）

#include<stdio.h>typedef struct point{int row, col;} item_t;#define MAX_ROW 5#define MAX_COL 5static item_t stack[512];static int top = 0;void push（item_t p）{stack[top++] = p;}item_t 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（"
"）;}printf（"*********
"）;}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）
", p.row, p.col）;while （predecessor[p.row][p.col].row ！= -1）{p = predecessor[p.row][p.col];printf（"（%d, %d）
", p.row, p.col）;}}elseprintf（"No path！
"）;return 0;}