- 论坛徽章:
- 0
|
现在我们用堆栈解决一个有意思的问题,定义一个二维数组:
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表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。
3、上一节我们实现了一个基于堆栈的程序,然后改写成递归程序,用函数调用的栈帧替代自己实现的堆栈。本节的DFS算法也是基于堆栈的,请把它改写成递归程序,这样改写可以避免使用predecessor数据结构,想想该怎么做。
倒序打印:- #include <stdio.h>
- #define MAX_ROW 5
- #define MAX_COL 5
- struct point { int row, col; };
- 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},
- };
- int explore(struct point p){
- if (p.row == MAX_ROW - 1 /* goal */
- && p.col == MAX_COL - 1)
- return 1;
- struct point next;
- if (p.col+1 < MAX_COL /* right */
- && maze[p.row][p.col+1] == 0){
- maze[p.row][p.col+1] = 2;
- next.row=p.row;
- next.col=p.col+1;
- if(explore(next)==1){
- printf("(%d, %d), ", next.row, next.col);
- return 1;
- }
- }
- if (p.row+1 < MAX_ROW /* down */
- && maze[p.row+1][p.col] == 0)
- {
- maze[p.row+1][p.col] = 2;
- next.row=p.row+1;
- next.col=p.col;
- if(explore(next)==1){
- printf("(%d, %d), ", next.row, next.col);
- return 1;
- }
- }
- if (p.col-1 >= 0 /* left */
- && maze[p.row][p.col-1] == 0)
- {
- maze[p.row][p.col-1] = 2;
- next.row=p.row;
- next.col=p.col-1;
- if(explore(next)==1){
- printf("(%d, %d), ", next.row, next.col);
- return 1;
- }
- }
- if (p.row-1 >= 0 /* up */
- && maze[p.row-1][p.col] == 0)
- {
- maze[p.row-1][p.col] = 2;
- next.row=p.row-1;
- next.col=p.col;
- if(explore(next)==1){
- printf("(%d, %d), ", next.row, next.col);
- return 1;
- }
- }
- return -1;
- }
- int main(void)
- {
- struct point p = { 0, 0 };
- if(explore(p)!=1){
- printf("no path!\n");
- }
- else
- printf("(%d, %d)\n", p.row, p.col);
- return 0;
- }
复制代码 |
|