- 注册时间
- 2004-10-13
- 最后登录
- 2019-5-15
⑧专业
*永恒国度*
- 积分
- 14145
|
关于队列里有这么一道例题 : 解迷宫问题:迷宫是如图示的m行n列的0-1矩阵,其中0表示无障碍,1表示有障碍.设入口为(1,1),出口为(m,n) , 每次移动只能从一个无障碍的单元移到其周围8个方向上任一无障碍的单元.
列号----> 1 2 3 4 5
行号-->1| 0 0 0 1 0
2| 0 1 0 0 0
3| 0 0 1 0 1
4| 1 1 0 1 0
5|
使用这样的数据结构:用数组mg[1..m, 1..n]表示迷宫,为了算法方便, 在四周加上一圈"哨兵",即变为数组
mg[0...m+1, 0...n+1]表示迷宫, 用数组zx, zy 分别表示 X, Y 方向的移动增量,如图示, 使用一个队列queue记录走过的点, 并用变量front, rear分别表示队列的首与尾.
队列的结构如下:
struct stype
{
int x, y,pre /*x,y为点的坐标, pre为到达本点的上一步步号*/
} queue[MaxSize];
图2:
方向 北 东北 东 东南 南 西南 西 西北
下标 1 2 3 4 5 6 7 8
zx -1 -1 0 1 1 1 0 -1
zy 0 1 1 1 0 -1 -1 -1
算法搜索过程: 首先从(1,1)处开始搜索,将其周围8个方向可走(为0值)的点均插入到队列queue中,pre为到达本点的上一步步号,也就是当前的front之值,并将该点赋值为-1,避免回来重复搜索.如果其中某点是出口,算法结束,根据 rear 指示的前驱步号可回溯得到走迷宫的最短路径;否则从队列 删除一个点,进入下一步,同样将其周围8个方向可走的点插入到队列中, pre为到达本点的上一步步号,也就是当前的front之值,并将该点赋值为-1,避免回来重复搜索.如果其中某点是出口,算法结束,根据 rear 指示的前驱步号可回溯得到走迷宫的最短路径;否则从队列 删除一个点,进入下一步 ,直到循环算法结束,如果queue队列中没有元素且末找到出口,则表示不存在路径.
图3:迷宫路径搜索过程
步号 x y pre
1 1 1 0
2 1 2 1
3 2 1 1
4 1 3 2
5 2 3 2
6 3 2 3
7 3 1 3
8 2 4 4
9 3 4 5
10 4 3 6
11 1 5 8
12 2 5 8
13 4 5 9
14 5 3 10
15 5 2 10
16 5 5 13
程序如下:- #include<stdio.h>
- #define m 5
- #define n 5
- #define MaxSize 100
- struct stype
- {
- int x,y,pre;
- }queue[MaxSize];
- int mg[m+1][n+1];
- int zx[8],zy[8];
- void printlj(int rear)
- {
- int i=rear,j;
- do /*反向找到最短路径,将路径上点的pre成员设置成-1*/
- {
- j=i;
- i=queue[i].pre;
- queue[j].pre=-1;
- }
- while (i!=0);
- printf("search the maze road:\n\t entry->");
- i=0;
- while(i<MaxSize) /*正向搜索pre为-1的点,构成正向路径*/
- {
- if(queue[i].pre==-1)
- printf("(%d,%d)->",queue[i].x,queue[i].y);
- i++;
- }
- printf("exit\n");
- }
- void mglj()
- {
- int i,j,x,y,v,front,rear,find=0;
- queue[1].x=1;queue[1].y=1;queue[1].pre=0; /*从(1,1)开始搜索,将该点插入队列*/
- front=1;rear=1; /*队列指针置初值1*/
- mg[1][1]=-1; /*将其赋值-1,避免回来重复搜索*/
- while(front<=rear && !find) /*队列不为空且末找到路径时循环*/
- {
- x=queue[front].x;
- y=queue[front].y;
- for(v=1;v<=8;v++) /*循环扫描每个方向,把每个可走方向插入队列*/
- {
- i=x+zx[v];j=y+zy[v]; /*选择一个前进方向(i,j) */
- if(mg[i][j]==0) /*如果该方向可走*/
- {
- rear++; /*将该方向插入队列*/
- queue[rear].x=i; /*将其赋值-1,避免重复搜索*/
- queue[rear].y=j;
- queue[rear].pre=front;
- mg[i][j]=-1;
- }
- if(i==m && j==n) /* 找到出口*/
- {
- printlj(rear); /*打印找到的路径*/
- find=1; /*设置为1退出循环*/
- }
- }
- front++; /*从队列中删除一个元素*/
- }
- if(!find) printf("no presence!\n");
- }
- void main()
- {
- int i,j;
- for(i=1;i<=m;i++)
- for(j=1;j<=n;j++) /*获取迷宫数据, 自己输入*/
- scanf("%d",&mg[i][j]);
- for(i=0;i<=m+1;i++)
- {
- mg[i][0]=1;mg[i][n+1]=1; /*加上为1的外框*/
- }
- for(j=0;j<=n+1;j++)
- {
- mg[0][j]=1;mg[m+1][j]=1;
- }
- zx[1]=-1;zx[2]=-1;zx[3]=0;zx[4]=1; /*建立方向数据*/
- zx[5]=1;zx[6]=1;zx[7]=0;zx[8]=-1;
- zy[1]=0;zy[2]=1;zy[3]=1;zy[4]=1;
- zy[5]=0;zy[6]=-1;zy[7]=-1;zy[8]=-1;
- mglj(); /*产生迷宫路径
- }
复制代码
问题:
1.首先对这程序的实现很难理解,不知从何入手,
2.开始时他所说的加上一圈"哨兵"是什么意思呢?
3.为什么要设图2 这样的移动增量?
4.图3的搜索过程怎么理解呢?
5.在mglj() 函数中为什么要用 front++ 来删除数据呢?
6.main函数里为什么要加上什么 1的外框?
7.他的结果(1,1)->(1,2)->(2,3)->(3,4)->(4,5)->(5,5) 到底是怎么判断得到的?? |
|