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

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

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

#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");
}

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