数据结构之求解迷宫问题Ⅱ

这次介绍用队列实现迷宫求解问题~
用栈解决迷宫问题用的是“穷举求解” 即从入口出发，顺某一方向试探，若能走通，则继续往前走，否则原路返回，换另一个方向继续试探，直至走出去。

用队列方式求解迷宫，其思想是将每个方块的所有可走路径均存放到队列中，采用限制条件避免重复搜索，最后求得最短路径。对应算法：
首先先定义个迷宫~

#define M 4
#define N 4
int mg1[M+2][N+2]={
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,0,0,0,1,1},
{1,0,0,0,0,1},
{1,1,1,1,1,1},
}

设置基本变量

int minlen=0;//最短路径长度
int num=1;//用来记录路径条数

队列输出路径

void print1(int front)
{
    int  k = front,j;   
    int ns = 0; //计算本次路径长度
    do{
    j=k;
    k=Qu[k].pre;
    ns++;
}while(k!=-1);
if (num==1) minlen=ns; //就是这条啦！
if(ns==minlen){      //去找第一条或者其他条
 ns = 0;
 k = front;
printf("第%d条最短路径（反向输出）:\n",num++);
do
{
j=k;
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
k=Qu[k].pre;
if(++ns%5==0) printf("\n");
}while(k!=-1);
printf("\n");
}

}

搜索路径

void mgpath1(int x1,int y1,int x2,int y2){  // 从(x1,y1)->(x2,y2)
int i,j,find=0,di,k;
rear++;
Qu[rear].i=x1;
Qu[rear].j=y1;
Qu[rear].pre=-1;                            //将（x1,y1）入队
while (front!=rear){                        //队列不为空，循环
front++;                                          //出队，元素仍在
for(di=0;di<4;di++){                       //循环扫描，把每一个可走的坐标插入队列
        switch(di){
            case 0:i=Qu[front].i-1;j=Qu[front].j;break;
            case 1:i=Qu[front].i;j=Qu[front].j+1;break;
            case 2:i=Qu[front].i+1;j=Qu[front].j;break;
            case 3:i=Qu[front].i,j=Qu[front].j-1;break;
        }
        if(i>0 && j>0 && mg1[i][j]==0 && (i!=Qu[Qu[front].pre].i || j!=Qu[Qu[front].pre].i)){//不越界且可走 以及避免回退
            rear++;     //相邻方块插入队列
            Qu[rear].i=i;Qu[rear].j=j;
            Qu[rear].pre=front;   //指向路径中上一个方块下标
            }
    }
}
    for(k=0;k<=rear;k++){
        if(Qu[k].i==x2&&Qu[k].j==y2){   //找到了
            find=1;
            print1(k);
            }
        }
    if(!find) printf("根本没有出口！\n");
}

就这样，一个队列的迷宫算法已经实现~~~