3.3 栈和队列求解迷宫问题
2016-10-10 18:54阅读：
2 用队列求解迷宫问题
数据组织
使用一个队列qu记录走过的方块，该队列的结构如下：
1. typedef
struct
2. {
3.
int i,j;
//方块的位置
4.
int pre;
//本路径中上一方块在队列中的下标
5. }Box;
6.
7. typedef
struct
8. {
9. Box
data[MaxSize];
10.
int front,rear;
int front,rear;
//队头指针和队尾指针
11. }QuType;
这里使用的队列qu不是环形队列（因为要利用出队的元素找路径），因此在出队时，不会将出队元素真正从队列中删除，因为要利用它输出路径。
算法设计
首先将入口进队。出队一个方块，考察如下：
所有搜索过的方块都在队列中。
最后通过队列找出出口—>入口的一条迷宫路径。
用队列求一条迷宫路径的算法：（xi，yi）——>（xe，ye）
1. bool
mgpath1(int
xi,int
yi,int
xe,int ye)
2. {
3.
int i,j,find=0,di;
4. QuType qu;
//定义顺序队
5. qu.front=qu.rear=-1;
6. qu.rear++;
7.
qu.data[qu.rear].i=xi;qu.data[qu.rear].j=yi;
//(xi,yi)进队
8.
qu.data[qu.rear].pre=-1;
9. mg[xi][yi]=-1;
//将其赋值-1，避免回过来重复搜索
10.
11.
while(qu.front!=qu.rear&&!find)
//队列不空循环
12. {
13.
qu.front++; //出队
14.
i=qu.data[qu.front].i;j=qu.data[qu.front].j;
15.
if(i==xe &&
j==ye)
//找到了出口，输出路径
16. {
17.
find=1;
18.
print(qu,qu.front);
19.
return
true;
20. }
21.
for(di=0;di<4;di++)
22. {
23.
switch(di)
24.
{
25.
case
0:
i=qu.data[qu.front].i-1;j=qu.data[qu.front].j;break;
26.
case
1:
i=qu.data[qu.front].i;j=qu.data[qu.front].j+1;break;
27.
case
2:
i=qu.data[qu.front].i+1;j=qu.data[qu.front].j;break;
28.
case
3:
i=qu.data[qu.front].i;j=qu.data[qu.front].j-1;break;
29.
}
30.
if(mg[i][j]==0)
31.
{
32.
qu.rear++;
//将该方块入队
33.
qu.data[qu.rear].i=i;
34.
qu.data[qu.rear].j=j;
35.
qu.data[qu.rear].pre=qu.font;
36.
mg[i][j]=-1;
37.
}
38. }
39. }
40.
return
false;
//未找到一条路径时返回false
41. }
对于上述迷宫（前一节用栈求解迷宫问题的迷宫），求解（1,1）—>（8,8）时队列qu中结果如下：
运行结果
显然，这个解是最优解，即最短路径。
思考题：
用队列和用栈求解迷宫问题有什么不同？
