走迷宮，depth first search，dfs，深度優(yōu)先搜索

blackfur

現(xiàn)在我們用堆棧解決一個有意思的問題，定義一個二維數(shù)組：

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、上一節(jié)我們實現(xiàn)了一個基于堆棧的程序，然后改寫成遞歸程序，用函數(shù)調(diào)用的棧幀替代自己實現(xiàn)的堆棧。本節(jié)的DFS算法也是基于堆棧的，請把它改寫成遞歸程序，這樣改寫可以避免使用predecessor數(shù)據(jù)結構，想想該怎么做。

倒序打�。�

1. #include <stdio.h>
   
2. 
   
3. #define MAX_ROW 5
   
4. #define MAX_COL 5
   
5. 
   
6. struct point { int row, col; };
   
7. int maze[MAX_ROW][MAX_COL] = {
   
8.     {0, 1, 0, 0, 0},
   
9.     {0, 1, 0, 1, 0},
   
10.     {0, 0, 0, 0, 0},
    
11.     {0, 1, 1, 1, 0},
    
12.     {0, 0, 0, 1, 0},
    
13. };
    
14. 
    
15. int explore(struct point p){
    
16.     if (p.row == MAX_ROW - 1  /* goal */
    
17.             && p.col == MAX_COL - 1)
    
18.         return 1;
    
19.     struct point next;
    
20.     if (p.col+1 < MAX_COL     /* right */
    
21.             && maze[p.row][p.col+1] == 0){
    
22.         maze[p.row][p.col+1] = 2;
    
23.         next.row=p.row;
    
24.         next.col=p.col+1;
    
25.         if(explore(next)==1){
    
26.             printf("(%d, %d), ", next.row, next.col);
    
27.             return 1;
    
28.         }
    
29.     }
    
30. 
    
31.     if (p.row+1 < MAX_ROW     /* down */
    
32.             && maze[p.row+1][p.col] == 0)
    
33.     {
    
34.         maze[p.row+1][p.col] = 2;
    
35.         next.row=p.row+1;
    
36.         next.col=p.col;
    
37.         if(explore(next)==1){
    
38.             printf("(%d, %d), ", next.row, next.col);
    
39.             return 1;
    
40.         }
    
41.     }
    
42. 
    
43.     if (p.col-1 >= 0          /* left */
    
44.             && maze[p.row][p.col-1] == 0)
    
45.     {
    
46.         maze[p.row][p.col-1] = 2;
    
47.         next.row=p.row;
    
48.         next.col=p.col-1;
    
49.         if(explore(next)==1){
    
50.             printf("(%d, %d), ", next.row, next.col);
    
51.             return 1;
    
52.         }
    
53.     }
    
54. 
    
55.     if (p.row-1 >= 0          /* up */
    
56.             && maze[p.row-1][p.col] == 0)
    
57.     {
    
58.         maze[p.row-1][p.col] = 2;
    
59.         next.row=p.row-1;
    
60.         next.col=p.col;
    
61.         if(explore(next)==1){
    
62.             printf("(%d, %d), ", next.row, next.col);
    
63.             return 1;
    
64.         }
    
65.     }
    
66.     return -1;
    
67. }
    
68. 
    
69. int main(void)
    
70. {
    
71.     struct point p = { 0, 0 };
    
72.     if(explore(p)!=1){
    
73.         printf("no path!\n");
    
74.     }
    
75.     else
    
76.         printf("(%d, %d)\n", p.row, p.col);
    
77.     return 0;
    
78. }

復制代碼

blackfur

廣度優(yōu)先法，breadth first search,bfs

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

復制代碼

linux_c_py_php

炫耀貼....