首页 > 开发 > C > 正文

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

2016-06-05 16:03:14  来源:慕课网
  这次介绍用队列实现迷宫求解问题~
用栈解决迷宫问题用的是“穷举求解” 即从入口出发,顺某一方向试探,若能走通,则继续往前走,否则原路返回,换另一个方向继续试探,直至走出去。
  用队列方式求解迷宫,其思想是将每个方块的所有可走路径均存放到队列中,采用限制条件避免重复搜索,最后求得最短路径。对应算法:
首先先定义个迷宫~
#define M 4#define N 4int 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");}  就这样,一个队列的迷宫算法已经实现~~~