linux C一站式学习

bellszhu

这本书的12.3节，例子12.3 用深度优先搜索解迷宫问题。。
个人觉得不是深度优先啊，而是广度优先呀。。请问是不是？
程序如下：

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

复制代码