Chinaunix

标题: 走迷宫，depth first search，dfs，深度优先搜索 [打印本页]

---

作者: blackfur    时间: 2013-10-26 20:40
标题: 走迷宫，depth first search，dfs，深度优先搜索
现在我们用堆栈解决一个有意思的问题，定义一个二维数组：

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数据结构，想想该怎么做。

倒序打印：

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    时间: 2013-10-26 21:29
广度优先法，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    时间: 2013-10-27 15:39
炫耀贴....

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2