[刷题] 走迷宫

用栈实现深度优先遍历
 1 #include <iostream>
 2 #define MAX_ROW 5
 3 #define MAX_COL 5
 4 
 5 struct point { int row, col; } stack[512];
 6 int top = 0;
 7 
 8 void push(struct point p)
 9 {
10     stack[top] = p;
11     top++;
12 }
13 
14 struct point pop(void)
15 {
16     top--;
17     return stack[top];
18 }
19 
20 int is_empty(void)
21 {
22     return top == 0;
23 }
24 
25 int maze[MAX_ROW][MAX_COL] = {
26     0,1,0,0,0,
27     0,1,0,1,0,
28     0,0,0,1,0,
29     0,1,1,1,0,
30     0,0,0,1,0,    
31 };
32 
33 void print_maze(void)
34 {
35     int i, j;
36     for(i = 0; i < MAX_ROW; i++){
37         for(j = 0; j < MAX_COL; j++)
38             printf("%d",maze[i][j]);
39         putchar('
');
40     }
41     printf("************
");
42 }
43 
44 struct point predecessor[MAX_ROW][MAX_COL] = {
45     {{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
46     {{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
47     {{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
48     {{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
49     {{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},    
50 };
51 
52 void visit(int row, int col, struct point pre)
53 {
54     struct point visit_point = { row, col};
55     maze[row][col] = 2;
56     predecessor[row][col] = pre;
57     push(visit_point);
58 }
59 
60 int main(void)
61 {
62     struct point p = { 0, 0};
63     
64     maze[p.row][p.col] = 2;
65     push(p);
66     
67     while (!is_empty()){
68         p = pop();
69         if (p.row == MAX_ROW - 1  /* goal */
70             && p.col == MAX_COL - 1)
71             break;
72         if (p.col+1 < MAX_COL     /* right */
73             && maze[p.row][p.col+1] == 0)
74             visit(p.row, p.col+1, p);
75         if (p.row+1 < MAX_ROW     /* down */
76             && maze[p.row+1][p.col] == 0)
77             visit(p.row+1, p.col, p);
78         if (p.col-1 >= 0          /* left */
79             && maze[p.row][p.col-1] == 0)
80             visit(p.row, p.col-1, p);
81         if (p.row-1 >= 0          /* up */
82             && maze[p.row-1][p.col] == 0)
83             visit(p.row-1, p.col, p);
84         print_maze();
85     }
86     if (p.row == MAX_ROW -1 && p.col == MAX_COL -1) {
87         printf("(%d,%d)
", p.row, p.col);
88         while(predecessor[p.row][p.col].row != -1) {
89             p = predecessor[p.row][p.col];
90             printf("(%d, %d)
",p.row, p.col);
91         }
92     }else
93         printf("No path!
");
94     
95     return 0;
96 }
结果：