1 问题

定义一个二维数组：

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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。[Linux C编程一站式学习 12.3题目，没读懂题目要求是找到所有的路线还是一条路线]。

2 用堆栈来实现深度优先过程

在迷宫中可以走的路（数组maze中值为0的元素的坐标）用堆栈数据结构保存[在迷宫中（数组中当前坐标为0的元素的坐标）先探索是否可以往右、下、左、上的顺序走，如果可以就将这些右边的、下边的、左边的、上面的元素的坐标记录下来]。然后再将栈顶的元素坐标取出来（上，左，下，右）按照相同的方式探索此元素周围的其它元素，当出现走不通情况时，由于堆栈的每次出栈操作，堆栈的下一次出栈操作就会使得另外一个方向的元素坐标被压出来。对于左和右来说，在迷宫中往上和下走总是优先，故而有深度优先的特点。

3  C代码 

平台：debain GNU/Linux 3.2.04

代码中将maze[4][3]由原来的1改为0，以验证程序向左和向上搜索通道。从左下角到右下角所有的通路代码：

1. /* platform：    debian  GNU/Linux 3.2.04 
2.  * filename:    deepth_fisrt.c 
3.  * brife:   Sovle the maze problem by using stack 
4.  * author:  One fish 
5.  * date:    2014.7.19 -- Saturday 
6.  */  
7. #include   
8.   
9.   
10.   
11. //--------------Macro definiton-----------------------------  
12. #define ROAD        0  
13. #define AREADY_WALK 2  
14. #define ROW     5  
15. #define COL     5  
16. #define N       ROW * COL  
17. //--------------Macro definiton-----------------------------  
18.   
19.   
20.   
21. /******************** Global varibales definition ************/  
22. static int maze[ROW][COL] = {  
23.     {0, 1, 0, 0, 0},  
24.     {0, 1, 0, 1, 0},  
25.     {0, 0, 0, 0, 0},  
26.     {0, 1, 1, 1, 0},  
27.     {0, 0, 0, 0, 0}  
28. };      //The maze, 0 is the road, 1 is the wall  
29.   
30.   
31. static int top; //Index of stack top's next location  
32. static struct point {  
33.     int row;  
34.     int col;  
35. }p, stack[N];   //p is the maze's location, stack is the location of maze's element which equals zero  
36. /******************** Global varibales definition ************/  
37.   
38.   
39.   
40. //------------------Function deckaration--------------------  
41. void go_maze(void);  
42. void maze_visit(int row, int col, struct point p);  
43. void print_maze(void);  
44. void stack_push(struct point p);  
45. struct point stack_pop(void);  
46. int stack_empty(void);  
47.   
48.   
49.   
50.   
51. int main(void)  
52. {  
53.     go_maze();  
54.   
55.     return 0;  
56. }  
57.   
58.   
59.   
60. /* @brife:  Print maze elements 
61.  * @arg:    None 
62.  * @rel:    None 
63.  */  
64. void print_maze(void)  
65. {  
66.     int i, j;  
67.     for(i = 0; i < ROW; ++i){  
68.         for(j = 0; j < COL; ++j)  
69.             printf("%d\t", maze[i][j]);  
70.         printf("\n");  
71.     }  
72.     printf("----------------------------------\n");  
73. }  
74.   
75. /* @brife:  Finde one road in maze 
76.  * @arg:    None 
77.  * @rel:    None 
78.  */  
79. void go_maze(void)  
80. {  
81.     //Init first element  
82.     p.row = p.col   = 0;  
83.     maze[p.row][p.col]  = AREADY_WALK;  
84.     stack_push(p);  
85.   
86.   
87.     while(!stack_empty()){  
88.         //The current location  
89.         p   = stack_pop();  
90.           
91.         //If only need one road  
92.         //if(ROW - 1 == p.row && COL - 1 == p.col)  
93.         //  break;  
94.         //Look if may go right direction  
95.         if(p.col < COL - 1 && ROAD == maze[p.row][p.col + 1]){  
96.             maze_visit(p.row, p.col + 1, p);  
97.         }  
98.           
99.         //Look if may go down  
100.         if(p.row < ROW - 1 && ROAD == maze[p.row + 1][p.col]){  
101.             maze_visit(p.row + 1, p.col, p);  
102.         }  
103.   
104.         //Look if may go left  
105.         if(p.col > 0 && ROAD == maze[p.row][p.col - 1]){  
106.             maze_visit(p.row, p.col - 1, p);  
107.         }  
108.   
109.         //Look if may go up  
110.         if(p.row > 0 && ROAD == maze[p.row - 1][p.col]){  
111.             maze_visit(p.row - 1, p.col, p);  
112.         }  
113.           
114.         //Show current element's road  
115.         print_maze();  
116.     }  
117. }  
118.   
119. /* @brife:  Mark(push in stack) the zero elments of stack, those elemets round the current element 
120.  * @arg:    row, col is the zero element(around the current elemet)'s row, col index.p is the current element's location 
121.  * @rel:    None 
122.  */  
123. void maze_visit(int row, int col, struct point p)  
124. {  
125.     struct point around_p = {row, col};  
126.     maze[row][col]  = AREADY_WALK;  
127.     stack_push(around_p);  
128. }  
129.   
130. /*@brife:   Push the p to stack top 
131.  *@arg:     p is the zero element of maze 
132.  *@rel:     None 
133.  */  
134. void stack_push(struct point p)  
135. {  
136.     if(top < N){  
137.         stack[top++]    = p;  
138.     }  
139. }  
140.   
141. /* @brife:  Get the top element of stack 
142.  * @arg:    None 
143.  * @rel:    The top element of stack if stack is not empty, -1 if stack is empty 
144.  */  
145. struct point stack_pop(void)  
146. {  
147.     if(!stack_empty()){  
148.         return stack[--top];  
149.     }else{  
150.         struct point p = {-1, -1};  
151.         return p;  
152.     }  
153. }  
154.   
155. /* @brife:  Judge if stack is empty 
156.  * @arg:    None 
157.  * @rev:    Stck is empty when return 1, oterwise return 0 
158.  */  
159. int stack_empty(void)  
160. {  
161.     if(top < 0)  
162.         return 1;  
163.     else  
164.         return 0;  
165. }  

在Linux终端下编译通过后并执行文件：

gcc   deepth_fisrt.c  -o  deepth_fisrt

./deepth_fisrt > all.txt

all.txt内容如下：

1. 2   1   0   0   0     
2. 2   1   0   1   0     
3. 0   0   0   0   0     
4. 0   1   1   1   0     
5. 0   0   0   0   0     
6. ----------------------------------  
7. 2   1   0   0   0     
8. 2   1   0   1   0     
9. 2   0   0   0   0     
10. 0   1   1   1   0     
11. 0   0   0   0   0     
12. ----------------------------------  
13. 2   1   0   0   0     
14. 2   1   0   1   0     
15. 2   2   0   0   0     
16. 2   1   1   1   0     
17. 0   0   0   0   0     
18. ----------------------------------  
19. 2   1   0   0   0     
20. 2   1   0   1   0     
21. 2   2   0   0   0     
22. 2   1   1   1   0     
23. 2   0   0   0   0     
24. ----------------------------------  
25. 2   1   0   0   0     
26. 2   1   0   1   0     
27. 2   2   0   0   0     
28. 2   1   1   1   0     
29. 2   2   0   0   0     
30. ----------------------------------  
31. 2   1   0   0   0     
32. 2   1   0   1   0     
33. 2   2   0   0   0     
34. 2   1   1   1   0     
35. 2   2   2   0   0     
36. ----------------------------------  
37. 2   1   0   0   0     
38. 2   1   0   1   0     
39. 2   2   0   0   0     
40. 2   1   1   1   0     
41. 2   2   2   2   0     
42. ----------------------------------  
43. 2   1   0   0   0     
44. 2   1   0   1   0     
45. 2   2   0   0   0     
46. 2   1   1   1   0     
47. 2   2   2   2   2     
48. ----------------------------------  
49. 2   1   0   0   0     
50. 2   1   0   1   0     
51. 2   2   0   0   0     
52. 2   1   1   1   2     
53. 2   2   2   2   2     
54. ----------------------------------  
55. 2   1   0   0   0     
56. 2   1   0   1   0     
57. 2   2   0   0   2     
58. 2   1   1   1   2     
59. 2   2   2   2   2     
60. ----------------------------------  
61. 2   1   0   0   0     
62. 2   1   0   1   2     
63. 2   2   0   2   2     
64. 2   1   1   1   2     
65. 2   2   2   2   2     
66. ----------------------------------  
67. 2   1   0   0   2     
68. 2   1   0   1   2     
69. 2   2   0   2   2     
70. 2   1   1   1   2     
71. 2   2   2   2   2     
72. ----------------------------------  
73. 2   1   0   2   2     
74. 2   1   0   1   2     
75. 2   2   0   2   2     
76. 2   1   1   1   2     
77. 2   2   2   2   2     
78. ----------------------------------  
79. 2   1   2   2   2     
80. 2   1   0   1   2     
81. 2   2   0   2   2     
82. 2   1   1   1   2     
83. 2   2   2   2   2     
84. ----------------------------------  
85. 2   1   2   2   2     
86. 2   1   2   1   2     
87. 2   2   0   2   2     
88. 2   1   1   1   2     
89. 2   2   2   2   2     
90. ----------------------------------  
91. 2   1   2   2   2     
92. 2   1   2   1   2     
93. 2   2   2   2   2     
94. 2   1   1   1   2     
95. 2   2   2   2   2     
96. ----------------------------------  
97. 2   1   2   2   2     
98. 2   1   2   1   2     
99. 2   2   2   2   2     
100. 2   1   1   1   2     
101. 2   2   2   2   2     
102. ----------------------------------  
103. 2   1   2   2   2     
104. 2   1   2   1   2     
105. 2   2   2   2   2     
106. 2   1   1   1   2     
107. 2   2   2   2   2     
108. ----------------------------------  
109. 2   1   2   2   2     
110. 2   1   2   1   2     
111. 2   2   2   2   2     
112. 2   1   1   1   2     
113. 2   2   2   2   2     
114. ----------------------------------  
115. 2   1   2   2   2     
116. 2   1   2   1   2     
117. 2   2   2   2   2     
118. 2   1   1   1   2     
119. 2   2   2   2   2     
120. ----------------------------------

多了几行。

从左下角到右下角深度优先一个通路代码只需要将从左下角到右下角所有的通路代码中void go_maze(void);函数中if语句的注释取消即可：

1. while(!stack_empty()){  
2.     //The current location  
3.     p   = stack_pop();  
4.       
5.     //If only need one road  
6.     //if(ROW - 1 == p.row && COL - 1 == p.col)  
7.     //  break;  
8.     //Look if may go right direction  
9.     if(p.col < COL - 1 && ROAD == maze[p.row][p.col + 1]){  
10.         maze_visit(p.row, p.col + 1, p);  
11.     }  

在Linux终端下编译通过后并执行文件：

gcc   deepth_fisrt.c  -o  deepth_fisrt 

./deepth_fisrt > once.txt 

once.txt内容如下：

1. 2   1   0   0   0     
2. 2   1   0   1   0     
3. 0   0   0   0   0     
4. 0   1   1   1   0     
5. 0   0   0   0   0     
6. ----------------------------------  
7. 2   1   0   0   0     
8. 2   1   0   1   0     
9. 2   0   0   0   0     
10. 0   1   1   1   0     
11. 0   0   0   0   0     
12. ----------------------------------  
13. 2   1   0   0   0     
14. 2   1   0   1   0     
15. 2   2   0   0   0     
16. 2   1   1   1   0     
17. 0   0   0   0   0     
18. ----------------------------------  
19. 2   1   0   0   0     
20. 2   1   0   1   0     
21. 2   2   0   0   0     
22. 2   1   1   1   0     
23. 2   0   0   0   0     
24. ----------------------------------  
25. 2   1   0   0   0     
26. 2   1   0   1   0     
27. 2   2   0   0   0     
28. 2   1   1   1   0     
29. 2   2   0   0   0     
30. ----------------------------------  
31. 2   1   0   0   0     
32. 2   1   0   1   0     
33. 2   2   0   0   0     
34. 2   1   1   1   0     
35. 2   2   2   0   0     
36. ----------------------------------  
37. 2   1   0   0   0     
38. 2   1   0   1   0     
39. 2   2   0   0   0     
40. 2   1   1   1   0     
41. 2   2   2   2   0     
42. ----------------------------------  
43. 2   1   0   0   0     
44. 2   1   0   1   0     
45. 2   2   0   0   0     
46. 2   1   1   1   0     
47. 2   2   2   2   2     
48. ----------------------------------  

数组中2表示走过的路，那么从左上角严着有2的路线到右下角都是迷宫中的通道。如果寻找通道的方法不变（右，下，左，上），继续寻找新道路的顺序也变为右，下，左，上，那么就可以实现广度优先搜索。队列就有先进先出的特性，故而只要将以上代码的数据结构换成队列，那么就可以实现广度优先搜索来解决迷宫问题。一般为了回收利用队列中的存储空间，会采用环形队列作为程序数据结构来解决问题。除此之外，在堆栈数据结构上改变寻找通道的顺序也可以实现广度优先搜索，队列也可以实现深度优先搜索（未编程验证）。