(三)1.2_迷宫求解(使用队列)
一.问题描述
1.迷宫问题.假设迷宫由m行n列构成,有一个入口和一个出口,入口坐标为(1,1),出口坐标为(m,n),设计一个算法,找出一条最短的路径,如果没有路径报告无法通过的信息.
2.输入m,n,用二维数组创建一个m行n列的迷宫
3.迷宫的任一位置(i,j)上均有八个可以移动的方向(上, 右上, 右, 右下, 下, 左下, 左, 左上)
二.思路分析
1.这里我们用队列实现(直形顺序队列才行,链式队列不行哦,往下看就知道为什么了),采用广度搜索,就是从走到的位置向四周扩散,直到扩散到出口,或者无法继续扩散.打个比方吧,我们在迷宫的入口通入大量的水,水会向四周扩散吧,假如有通路,那么肯定有水流到出口对吧,可能不止一条通路,但水的流速是一样的,所以水最先流到出口的那条路径就是最短的路径,.
2.代码里这样实现,用int Maze[m+2][n+2]表示一个m*n的迷宫,如果是可通过的位置,则值为0,
如果是不能通过的位置,值为1.为什么数组大小要+2呢?这是把第0行,第0列和第m+1行,第n+1列作为围墙,表示不能出界呀,为了方便算法的实现. 所以这里围墙位置的值当然是要设为1.
3.我们把入口位置入队,然后队列非空循环,把队头的元素出队,然后顺时针遍历出队元素的相邻八个方向的位置(逆时针也可以),如果是可以通过的位置,则位置入队.遍历完了八个方向的位置后,我们再次循环,又出队一个元素,遍历它的八个位置…就这样循环,直到队列为空或者找到了出口
4.这里我们为了避免会在一个环形路径里打转,所以我们要有一个标记数组Mark[m+1[n+1] (0单元是不用的),把走过的位置标记一下(这里标记为1),下次遍历到该位置,如果已经被标记过了,则不能入队,避免重复走导致绕圈打转
5.还有非常重要的一点,存储位置信息的元素里面,我们不仅要存储当前的位置信息,我们还要存储此位置的先前位置在队列顺序表中的位置索引序号.因为我找到路径后,我们要回溯路径啊(从出口逆寻到入口),我们从出口开始,用上面说的先前位置的索引序号,我们就可以找到上一个位置了,这个位置元素同时也存储了它的上一个位置的索引序号,然后就这样继续逆寻,就能把这条路径还原了.这里我们每回溯一个位置就把位置存储到栈内(利用栈先进后出的特点),这样我们输出路径(出栈操作)的时候就是正向的了(从入口到出口)
注意: 上面说到必须是直形顺序队列才行,这是因为链式队列出队会把元素删除,这样我们回溯是找不到原来的位置元素的,因为被删除了呀,而直形顺序队列用的顺序表实现,出队实际上并没有删除元素,只是队头的位置发生了改变,之前存储的元素仍然在顺序表中,我们可以通过索引序号获得元素
三.代码实现
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#include"SqQueue.h"
#include"SqStack.h"
//位置类型
typedef struct
{
int i; //行
int j; //列
int pre; //前一个位置节点的序号
}POS; //position缩写
//迷宫类型
typedef struct
{
int **maze; //迷宫数组指针,二级指针
int row; //迷宫行数
int col; //迷宫列数
int start_i; //起点行位置
int start_j; //起点列位置
int end_i; //终点行位置
int end_j; //终点列位置
}MazeType;
//随机产生迷宫
void CreateMaze(MazeType *M)
{
int row=M->row; //迷宫行数
int col=M->col; //迷宫列数
int S_i=M->start_i; //迷宫起点行位置
int S_j=M->start_j; //迷宫起点列位置
int E_i=M->end_i; //迷宫终点点行位置
int E_j=M->end_j; //迷宫终点点行位置
//行列数量都加2,为了加上迷宫的四条边界,方便操作
//M->maze是二级指针
M->maze=(int**)malloc(sizeof(int*)*(row+2)); //分配行空间,实际上是存储所有列指针的空间,大小等于列指针大小乘以行指针数量,也就是行数
for(int r=0;r<=row+1;r++)
M->maze[r]=(int*)malloc(sizeof(int)*(col+2)); //依次给每行的列分配列空间,实际上是分配一行元素的存储空间,大小等于列的数量
int **maze=M->maze; //迷宫指针
//随机创建迷宫,位置为0,1分别表示可通过,不可通过
int i,j;
for(i=0;i<=row+1;i++) //行循环
{
for(j=0;j<=col+1;j++) //列循环
{
if(i==0||i==row+1||j==0||j==col+1) //边界位置不可通过
maze[i][j]=1;
else if((i==S_i&&j==S_j)||(i==E_i&&j==E_j)) //如果是起点或者终点位置要设置可以通过
{
maze[i][j]=0;
}
else //迷宫中的位置(不包括起点,终点);
{ // maze[i][j]=0;
maze[i][j]=rand()%2; //位置是否能通过随机设置
}//else
}//内for
}//外for
}
//销毁迷宫
void DestoryMaze(MazeType *M)
{
for(int j=M->col+1;j>=0;j--)
free(M->maze[j]); //先删除列内存
free(M->maze); //再删除行内存,实际删除的是存储列指针的内存空间
}
//显示迷宫
void PrintMaze(MazeType *M)
{
int **maze=M->maze; //指向迷宫的指针
int row=M->row; //迷宫行数
int col=M->col; //迷宫列数
printf("\n");
for(int i=1;i<=row;i++) //打印迷宫
{
for(int j=1;j<=col;j++)
{
if(maze[i][j]==1) //位置不通用实心方块显示
printf("■");
else //位置可通用空心方块显示
{
printf("□");
}
}
printf("\n");
}
}
//寻找路径
void SearchPath(MazeType *M,SqStack<POS>* S)
{
int row=M->row; //迷宫行数
int col=M->col; //迷宫列数
int S_i=M->start_i; //迷宫起点行位置
int S_j=M->start_j; //迷宫起点列位置
int E_i=M->end_i; //迷宫终点点行位置
int E_j=M->end_j; //迷宫终点点行位置
int **MAZE=M->maze; //迷宫指针
SqQueue<POS> Que; //创建一个队列(直形顺序队列)
SqQueue<POS>* Q=&Que; //创建一个指针指向生成的队列
InitQueue(Q,col*row); //初始化分配空间
//方向操作,分别是 0上, 1右上, 2右, 3右下, 4下, 5左下, 6左, 7左上
int Direction[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
//标记数组,初始值为0,在寻找路径通过了位置(i,j),则将MARK[i][j]置为1,为了便于理解,0单元不用,所以长宽各加一
int MARK[row+1][col+1]={0};
int i=S_i,j=S_j; //起点位置的行和列
POS e={i,j,-1}; //搜索的位置
EnQueue(Q,e); //入口位置入队
MARK[i][j]=1; //标记为已经经过
int Dir,pre; //遍历的方向,遍历到的位置元素的前一位置元素在队列中的序号
bool find=0; //是否搜寻到出口路径
POS NextPos; //要遍历的位置节点元素
while(!QueueEmpty(Q)&&!find) //当没有遍历到终点时,且队列中还有元素没出队搜索时;find为真说明搜索到了终点,队空说明没有通路
{
pre=Q->front; //遍历到的位置元素的前一位置元素在队列中的序号,它在队头位置的序号;
DeQueue(Q,e); //队元素出队
for(Dir=0;Dir<=7;Dir++) //搜索八个方向
{
NextPos={e.i+Direction[Dir][0],e.j+Direction[Dir][1],pre}; //遍历的位置等于出队的元素加上偏移量,前序号等于出队元素的位置序号
if(MAZE[NextPos.i][NextPos.j]==0&&MARK[NextPos.i][NextPos.j]==0) //如果道路可通,且没有经过
{
EnQueue(Q,NextPos); //可通位置入队
i=NextPos.i; //记住遍历的行
j=NextPos.j; //记住遍历的列
MARK[i][j]=1; //标记已经走过
if(i==E_i&&j==E_j) //如果找到出口了
{
find=1; //find为真
Q->front=Q->rear-1; //避免终点之前那些没出队的会被使用,所以把这个终点置为表头元素
break; //就退出循环
}
}//if
}//for
}//while
if(find) //如果find为真显示找到路径
{
printf("\nfind path!");
}
else //如果find为假显示没有路径
{
printf("\nno path!");
}
//回溯位置,存储路径到栈内
for(int k=Q->front;k<Q->rear;k++) //队列未空时进行
{
POS LastPos; //上一个位置元素
pre=Q->front; //上一位置的序号,现在初始是终点的位置序号,因为终点位置也要进栈存储
DeQueue(Q,e); //终点位置元素出队
for(pre=pre;pre!=-1;pre=LastPos.pre)
{
LastPos=Q->data[pre]; //用上一位置的序号来获得上一位置元素
Push(S,LastPos); //路径元素从终点到起点依次进栈
}
}//for
DestoryQueue(Q); //销毁队列
}
//显示路径
void PrintPath(SqStack<POS>* S)
{
POS NextPos; //下一个位置
if(!StackEmpty(S)) //如果有路径
printf("\npath:"); //显示路径
while(!StackEmpty(S))
{
Pop(S,NextPos); //退栈打印路径,利用了栈先进后出的特点
printf("->(%d,%d)",NextPos.i,NextPos.j);
}
}
int main()
{
srand(time(NULL)); //随机数种子
s1: printf("\n请输入迷宫的行数和列数:");
int row,col; //迷宫行数,列数
scanf("%d %d",&row,&col); //输入行数,列数
MazeType maze={NULL,row,col,1,1,row,col}; //定义迷宫类型,迷宫指针,行数,列数,起点行,列,终点行,列
CreateMaze(&maze); //根据迷宫类型创建迷宫
PrintMaze(&maze); //在屏幕显示迷宫
SqStack<POS> path; //构建一个栈来存储路径
InitStack(&path,row*col); //初始化栈
SearchPath(&maze,&path); //搜索路径,如果有路径存在,则把路径存入栈内
PrintPath(&path); //显示路径
DestoryMaze(&maze); //销毁迷宫
DestoryStack(&path); //销毁栈
getchar();
getchar();
goto s1;
return 0;
}
操作结果
四.相关提示
1.代码里的队列是用我自己写的一个队列模板头文件里的,这里没有附上其头文件,故代码在读者电脑上无法直接运行.读者需替换成自己创建的队列即可