栈的应用——迷宫问题

这里结合了栈+深度优先算法+回溯，难点在搜索迷宫路径

一 搜索迷宫路径思想如下：

从迷宫入口进入之后，从这里开始搜索其上下左右是否有障碍，如不是障碍就移动到这个位置上，并把该位置入栈，并从它开始继续搜索，若是障碍就选择另外一个方向，为了防止出现重复搜索，定义一个与迷宫大小相等的标记数组，将有障碍的和已经走过的位置标记为1（障碍），同时保留搜索的路径痕迹，在搜索下一个位置之前，将当前位置保存在栈中，如果所有相邻的非障碍位置都被搜索过仍未找到通往出口的路径，回退到上次的位置，并把回退前位置标记消除，再查看这个位置的其他方向是否被搜索过，如果所有的回退都被搜索过则表明不存在入口到出口的路径，这就是深入优先搜索算法。
简而言之，搜索路径就是顺着一个方向前进探索，若能走通则继续前进，否则回退到上一个位置。这里就需要使用栈的FILO特性

二 完整代码

[cpp] view plain copy

1. /*利用深度优先算法+堆栈+回溯算法求解迷宫问题*/  
2. #include <stdio.h>  
3. #include <stdlib.h>  
4. #include <string.h>  
5. #include <memory.h>  
6. #define MAXLENTH 51  
7. struct point  
8. {  
9.     int x;  
10.     int y;  
11. }Point[100];//定义坐标，记录走出迷宫路线  
12. char Maze[MAXLENTH][MAXLENTH];//定义存储迷宫的数组  
13. int visited[MAXLENTH][MAXLENTH],top = -1,row,col,flag = 0;  
14. //visited数组标记是否走过或者有障碍，top为栈顶，row col为迷宫的  
15. //行列，flag标记是否有通路到达出口  
16. int direction[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//定义四个行走方向,上下前后  
17.   
18. void push(int x,int y)//进栈函数  
19. {  
20.     Point[++top].x = x;  
21.     Point[top].y = y;  
22. }  
23.   
24. void pop()//出栈函数  
25. {  
26.     top--;  
27. }  
28.   
29. void Depth_First_Search(int x,int y)//对迷宫进行深度优先搜索  
30. {  
31.     int a,b,i;  
32.     if(Maze[x][y]=='E')  
33.     {  
34.         flag = 1;//到达出口，标记为1；  
35.         return;  
36.     }  
37.     for(i=0;i<4;i++)//从该坐标的四个方向进行搜索  
38.     {  
39.         a = x + direction[i][0];  
40.         b = y + direction[i][1];  
41.         if(a>0&&a<=row&&b>0&&b<=col&&!visited[a][b])  
42.         {//下一步走的方向需要满足坐标不能超越迷宫范围且没有走过或者有障碍  
43.             visited[a][b] = 1;//先标记走过  
44.             push(a,b);  
45.             Depth_First_Search(a,b);//递归，继续搜索  
46.             if(flag)  
47.                 return;//找到入口了  
48.             visited[a][b] = 0;//当前路不通且没有达到出口，回退，搜索下一个方向  
49.             pop(); //不是正确路径不保存  
50.         }  
51.     }  
52. }  
53. void output()//输出函数  
54. {  
55.     int i;  
56.     if(!flag)  
57.         printf("没有到达出口的通路\n");  
58.     else  
59.     {  
60.         printf("从入口走到出口的路线为；\n");  
61.         for(i=0;i<=top;i++)  
62.         {  
63.             printf("(%d,%d)",Point[i].x,Point[i].y);  
64.             if(i!=top)  
65.                 printf("->");  
66.         }  
67.         printf("\n");  
68.     }  
69. }  
70.   
71. int   main()  
72. {  
73.     int i,j,x,y;  
74.     printf("输入迷宫的行数row和列数col:\n");  
75.     scanf("%d%d",&row,&col);  
76.     memset(visited,0,sizeof(visited));  
77.     /*void *memset(void *s, int ch, unsigned n); 
78.     将s所指向的某一块内存中的每个字节的内容全部设置为ch指定的ASCII值, 
79. 　　块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作, 
80. 　　其返回值为指向S的指针。*/  
81.     getchar();  
82.     printf("输入迷宫分布图S表示入口,E表示出口，1表示障碍，0代表通路\n");  
83.     for(i=1;i<=row;i++)//输入迷宫分布图  
84.     {  
85.         for(j=1;j<=col;j++)  
86.         {  
87.             scanf("%c",&Maze[i][j]);  
88.             if(Maze[i][j]=='1')  
89.                 visited[i][j] = 1;  
90.             else if(Maze[i][j]=='S')//找到入口  
91.             {  
92.                 x = i;  
93.                 y = j;  
94.             }  
95.         }  
96.         getchar();  
97.     }  
98.     visited[x][y] = 1;//走过的标记为1  
99.     push(x,y);//坐标入栈  
100.     Depth_First_Search(x,y); //从入口开始搜索  
101.     output(); //输出  
102.     return 0;  
103. }  

结果

转载：http://blog.csdn.net/xsf50717/article/details/39962211