新浪博客

3.3 栈和队列求解迷宫问题

2016-10-10 18:53阅读：

http://blog.sina.cn/dpool/blog/u/3702337543

3.3 栈和队列求解迷宫问题
栈和队列都是存放多个数据的容器。通常用于存放临时数据：
①　如果先放入的数据先处理，则用队列。
②　如果后放入的数据先处理，则使用栈。
1 用栈求解迷宫问题
问题描述
给定一个M×N的迷宫图、入口和出口、行走规则。求一条从指定入口到出口的路径。所求路径必须是简单路径，即路径不重复。
行走规则：上、下、左、右相邻方块行走。其中（i，j）表示一个方块
3.3 <wbr>栈和队列求解迷宫问题


例如，M=8，N=8，图中的每个方块，可用空白表示通道，用阴影表示障碍物。为了算法方便，一般在迷宫外围加上一条围墙。


3.3 <wbr>栈和队列求解迷宫问题
数据组织
设置一个迷宫数组mg，其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时对应方块不可走。
3.3 <wbr>栈和队列求解迷宫问题

3.3 <wbr>栈和队列求解迷宫问题
在算法中用到的栈采用顺序栈存储结构，即将栈定义为：
1. typedef struct
2. {
3. int i; //当前方块的行号
4. int j; //当前方块的列号
5. int di; //di是下一可走相邻方位的方位号
6. }Box; //定义方块类型
7.
8. typedef struct
9. {
10. Box data[MaxSize];
11. int top; //栈顶指针
12. }StType; //定义顺序栈类型
算法设计
试探方向：从方位0开始，顺时针方向
3.3 <wbr>栈和队列求解迷宫问题
初始时，入口（i，j）作为当前方块。
3.3 <wbr>栈和队列求解迷宫问题
所有走过的方块都会进栈！
如果一个当前方块（i，j）找到一个相邻可走方块（x，y），就继续从（x，y）走下去。
3.3 <wbr>栈和队列求解迷宫问题

如果一个当前方块（i，j）没有找到一个相邻可走方块（x，y），表示此时无路可走，将其退栈。
3.3 <wbr>栈和队列求解迷宫问题
求解迷宫路径的过程：
3.3 <wbr>栈和队列求解迷宫问题
用栈求一条迷宫路径的算法：（xi，yi）——>（xe，ye）
1. bool mgpath(int xi,int yi,int xe,int ye)
2. {
3. int i,j,k,di,find;
4. StType st;
5. st.top=-1; //定义栈st并初始化
6. st.top++; //初始方块进栈
7. st.data[st.top].i=xi; st.data[st.top].j=yi;
8. st.data[st.top].di=-1;
9. mg[xi][yi]=-1; //为避免重复，当方块进栈时，将迷宫值改为-1
10.
11. while(s.top>-1) //栈不空时循环
12. {
13. i=st.data[st.top].i;
14. j=st.data[st.top].j;
15. di=st.data[st.top].di; //取栈顶方块
16. if(i==xe&&j==ye) //找到了出口，输出路径
17. {
18. printf('迷宫路径如下：');
19. for(k=0;k<=st.top;k++)
20. {
21. printf('%t(%d,%d) ',st.data[k].i,st.data[k].j );
22. if(k%5==0) //每行输出5个方块
23. printf('');
24. }
25. printf('');
26. return true;
27. }
28. find=0;
29. while (di<4 && find==0) //找下一个可走方块
30. {
31. di++;
32. switch(di)
33. {
34. case 0: i=st.data[st.top].i-1; j=st.data[st.top].j;break;
35. case 1: i=st.data[st.top].i; j=st.data[st.top].j+1;break;
36. case 2: i=st.data[st.top].i+1; j=st.data[st.top].j;break;
37. case 3: i=st.data[st.top].i; j=st.data[st.top].j-1;break;
38. }
39. if(mg[i][j]==0) find=1; //找到了下一个可走相邻方块（i，j）
40. }
41. if(find==1) //找到了下一个可走方块
42. {
43. st.data[st.top].di=di; //修改原栈顶元素的di值
44. st.top++; //下一个可走方块进栈
45. st.data[st.top].i=i;
46. st.data[st.top].j=j;
47. st.data[st.top].di=-1;
48. mg[i][j]=-1; //避免走到该方块
49. }
50. else //没有路径可走，则退栈
51. {
52. mg[st.data[st.top].i][st.data[st.top].j]=0; //让该位置变为其他路径可走方块
53. st.top--;
54. }
55. }
56. return false;
57. }
设计求解程序
建立如下主函数调用上述算法
1. void main()
2. {
3. if(!mgpath(1,1,M,N))
4. printf('该迷宫问题没有解！');
5. }
运行结果
对于上述迷宫，求解结果如下：
3.3 <wbr>栈和队列求解迷宫问题
3.3 <wbr>栈和队列求解迷宫问题
显然，这个解不是最优解 ，即不是最短路径。

我的更多文章

下载客户端阅读体验更佳

APP专享