数据结构 | 迷宫问题【栈与队列的交际舞】
【摘要】 通过栈与队列两种数据结构去实现迷宫问题路径得求解，人生真的在走迷宫吗？
@TOC
🌳堆栈实现
🥥思路分析
首先我们来看一下要如何使用堆栈去实现这个迷宫的求解
- 首先我们应该先模拟出一个迷宫来，一般的小型迷宫都是8x8，这个我们可以用数组来实现，定义一个mg[][]的二维数组，将墙标记为1，将可走路径标记为0，就有了下面的这个声明:point_down:
int mg[M + 2][N + 2] =
{ {1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
- 因为是四周的墙需要占位置，所以真正的迷宫入口是从mg[1][1]开始的，而出口所在出则是mg[8][8]，画了一张图将这个代码可视化一下:smile:
- 当我们有了一个整体的迷宫框架后，接下去我们就要在迷宫内部做文章，去寻找一条入口到出口的路径，那要如何去寻找呢？
- 这里我们先讲一种堆栈的实现方法，比较简洁易懂一些，然后我们再将如何用队列去将其实现
- 对于迷宫，我们都知道，里面是由一个个方块组成的，而对于每一个方块，则可以进行【上】【左】【下】【右】去行走。用堆栈去实现的话就是采用【穷举法】，往一个方向去走走看，若是可走，那就直接走，完全不管任何其他的方块是否也可以走；若是某个方块没有相邻的可走方块，则沿着原路返回前一个方块，换下一个方位继续寻找，直到把所有的通路都去走一遍
那有些小伙伴就很以后，这要怎么去回退呢?都已经走过了还怎么回去呀
- 这就要涉及到堆栈的知识了，我们要将走过的方块都放进一个栈里，对于栈我们都很清楚，是先进后出【FILO】的，最后只需要逆序打印即可找到一条完整的路径。当我们需要退回上一个方块的时候，只需要出栈当前栈顶元素即可。当然这种回退的思想也可以成为是【回溯】，这是属于搜索算法的一种，以下就是它的实现原理📕
🥥结构声明与框架推敲
了解了它的实现原理，接下来让我们一起来看一下怎么声明出它的结构
typedef struct {
int i; //当前方块的行号
int j; //当前方块的列号
int di; //下一相邻可走方位的方位号
}Box;
typedef struct {
Box data[MAX]; //数据
int top; //栈顶指针
}SqStack;
- 我们来分析一下以上代码，首先对于第一个结构体Box，其实值得就是迷宫中的方块它具有行号和列号，以及di下一相邻可走方位的方位号，这个di值得就是direction方位的意思
- 然后是第二个结构体，可以看出，这和我们顺序栈的定义方法类似，知识数据类型换成了Box方块类型，栈顶指针还是一张存在
接下来就是正常的顺序栈的各种实现方式，用于我们将迷宫中的方块放入以及拿出堆栈
/*初始化栈*/
void InitStack(SqStack*& s)
{
s = (SqStack*)malloc(sizeof(SqStack));
s->top = -1; //初始化栈中无元素
}
/*摧毁栈*/
void DestroyStack(SqStack*& s)
{
free(s);
}
/*判断栈是否为空*/
bool StackEmpty(SqStack* s)
{
return s->top == -1; //等于-1则表示栈为空
}
/*入栈*/
bool Push(SqStack*& s, Box e)
{
if (s->top == MAX - 1) //说明当前栈已满
return false;
s->top++; //需要入栈，要先在栈中开辟一个顶端元素
s->data[s->top] = e; //将给到的e赋值进对应的数据仓
return true;
}
/*出栈*/
bool Pop(SqStack*& s, Box& e)
{
if (s->top == -1) //说明当前栈无元素可出栈
return false;
e = s->data[s->top];
s->top--;
return true;
}
/*获取栈顶元素*/
bool GetTop(SqStack* s, Box& e)
{
if (s->top == -1) //说明当前栈无元素可出栈
return false;
e = s->data[s->top];
//s->top--; 获取栈顶元素不会减少栈中的元素
return true;
}
/*显示栈*/
void DisplayStack(SqStack* s)
{
int i = 0;
while (i <= s->top)
{
printf("%d ", s->data[i++]);
}
printf("\n");
}
以上代码不做过多解释，接下来我们来构思一下大体要实现的代码框架体系
- 我们需要一个专门求解path的函数，其传入值有入口的坐标以及出口的坐标。我们将求解路径的步骤分为以下四步
- 第一步我们应该要做一些初始化，例如定义一些我们可能会用到的变量，以及将入口先行入栈
- 第二步开始就需要去求解路径了，拿出栈顶方块判断其方位是否是出口，如果是的，则进行一系列的操作将对应的路径输出
- 第三步要去判断若是刚开始没有找到所需要的出口，那如何往四个方位去遍历，并且记录下可以走的方块
- 最后一步去判断是否找到了一个可走方块，若是，则其进栈，为我们输出路径做铺垫；若不是，则将其出栈，并且重置
🥥代码细究与分析
清楚了结构的声明以及代码逻辑的实现，接下去我们就要通过代码去实现找出这条实现路径
第一步
首先第一步是初始化以及将入口入栈
//1.初始化操作
bool MyPath(int xi, int yi, int xo, int yo)
{
Box path[MAX], e;
bool find;
int i, j, di,k;
SqStack* st; //存放迷宫方块的堆栈
InitStack(st);
e.i = xi;
e.j = yi; //设e为入口
e.di = -1; //初始化时出口e无下一个可走方块
Push(st, e);
mg[xi][yi] = -1; //将入口入栈后即表示此处不可再走
- 可以看到，我使用Box去定义了一个path路径，用于保存找到的那一条迷宫路径，e的话是我们每次要操作入栈出栈的方块，对于find，可以看到这是一个bool类型，用于标记是否找到了一个可走的方块
- 然后将给到的入口值给到e，再将e入栈即可，为什么要讲mg[xi][yi]迷宫中入口的值置为-1呢，因为我们用-1表示这个方块已经被走过了，不可以再走，不然的话后面在回溯的时候就会很麻烦，一直来回寻找，所以我们在后面也设置了重置一个方块是否可走，也就是重置为0
然后第二步就是要判断是否到达出口并且打印输出路径
while (!StackEmpty(st))
{
//2.若有一条可输出路径，则打印
//获取栈顶元素
GetTop(st, e);
i = e.i; j = e.j; di = e.di;
//若取出的栈顶元素为迷宫的一条路径，则进行输出
if (i == xo && j == yo)
{
puts("找到一条迷宫路径如下");
k = 0;
while (!StackEmpty(st))
{
Pop(st, e); //出栈栈顶元素
path[k++] = e; //将从栈顶取出的迷宫方块依此放入path路径中
}
//逆序，输出路径
while (k >= 1)
{
k--;
printf("\t(%d,%d)", path[k].i, path[k].j);
if ((k + 2) % 5 == 0)
printf("\n");
}
printf("\n");
DestroyStack(st);
return true;
}
- 首先我们要去获取当前的栈顶元素，然后判断其是否为出口，若是，则进入以下操作，因为此时既然找到了栈中的栈顶元素为迷宫的出口，那么则表示底下就都是迷宫过来所对应的方块，将其一一出栈然后放入路径中即可
- 最后通过逆序的方式将其打印输出就是我们所要的迷宫路径，当然若是找到了这么一条迷宫路径，就需要销毁堆栈返回true
接着第三步就是判断若是没有找到所需要的出口，那如何往四个方位去遍历
//3.若还未找到可走方块，则继续往四周寻找
int i1 = 0, j1 = 0; //用于存放下一个可走方块的位置
find = false;
while (di < 4 && !find)
{
di++;
switch (di)
{
case 0:i1 = i - 1; j1 = j; break;
case 1:i1 = i; j1 = j + 1; break;
case 2:i1 = i + 1; j1 = j; break;
case 3:i1 = i; j1 = j - 1; break;
}
if (mg[i1][j1] == 0) find = true;
}
- i1和j1是我们在搜寻完后存放的下一个可走方块的位置下标，看到while循环，当di < 4并且还没找到的时候将进入循环去下一个方块，因为一个方块分别对应四个方位，这里我们用switch去判断获取每一个方位的坐标位置，然后每次进入循环的时候都会顺着当前方块继续向下寻找，直到找到一个可走的方块并且这个di值到达4，因为如果4个方位都找遍了还没有找到，是没有第5个方位给你去寻找的
- 可以看到，在循环内部有一个if判断，这就是去判断当前方位是否可走也及时0，若是的，则表示找到了，让find置为true
最后是第四步去判断是否找到了一个可走方块，然后对应地进行操作
//4.判断栈中方块是否可走
if (find) { //若当前方块可走
st->data[st->top].di = di;
e.i = i1; e.j = j1; e.di = -1;
Push(st, e);
mg[i1][j1] = -1;
}
else { //若当前方块不可走
Pop(st, e); //将当前方块出栈
mg[e.i][e.j] = 0; //将当前方块的位置复原，供其他路径使用
}
- 可以看到，若是当前方块可走，我们就获取下一个可走方块的方位号，然后将其入栈然后将其再设置为不可走就行；若是当前方块不可走，则将当前方块出栈，然后重置这个方块在迷宫中的路径值即可，这样万一其他路径过来的时候这个方块也可以被使用
🥥结果测试及整体代码展示
了解了整体的代码逻辑，接下去我们将这个代码进行一个结果的测试:newspaper:
-
从结果看来我们是成功了，打印除了一条从入口到出口，从（1,1）到（8,8）的路径，每行输出5个，大家也可以去自己的编译器上运行一下看看
-
下面是整体的代码展示，供需要的小伙伴测试
#pragma once
#include <stdio.h>
#include <malloc.h>
#define M 8
#define N 8
#define MAX 100
typedef struct {
int i; //当前方块的行号
int j; //当前方块的列号
int di; //下一相邻可走方位的方位号
}Box;
typedef struct {
Box data[MAX]; //数据
int top; //栈顶指针
}SqStack;
/*初始化栈*/
void InitStack(SqStack*& s)
{
s = (SqStack*)malloc(sizeof(SqStack));
s->top = -1; //初始化栈中无元素
}
/*摧毁栈*/
void DestroyStack(SqStack*& s)
{
free(s);
}
/*判断栈是否为空*/
bool StackEmpty(SqStack* s)
{
return s->top == -1; //等于-1则表示栈为空
}
/*入栈*/
bool Push(SqStack*& s, Box e)
{
if (s->top == MAX - 1) //说明当前栈已满
return false;
s->top++; //需要入栈，要先在栈中开辟一个顶端元素
s->data[s->top] = e; //将给到的e赋值进对应的数据仓
return true;
}
/*出栈*/
bool Pop(SqStack*& s, Box& e)
{
if (s->top == -1) //说明当前栈无元素可出栈
return false;
e = s->data[s->top];
s->top--;
return true;
}
/*获取栈顶元素*/
bool GetTop(SqStack* s, Box& e)
{
if (s->top == -1) //说明当前栈无元素可出栈
return false;
e = s->data[s->top];
//s->top--; 获取栈顶元素不会减少栈中的元素
return true;
}
/*显示栈*/
void DisplayStack(SqStack* s)
{
int i = 0;
while (i <= s->top)
{
printf("%d ", s->data[i++]);
}
printf("\n");
}
#include <stdio.h>
#include "stack.hpp"
//自己绘制一条迷宫路径
int mg[M + 2][N + 2] =
{ {1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
//求解路径
bool MyPath(int xi, int yi, int xo, int yo)
{
//1.初始化操作
Box path[MAX], e;
bool find;
int i, j, di,k;
SqStack* st; //存放迷宫方块的堆栈
InitStack(st);
e.i = xi;
e.j = yi; //设e为入口
e.di = -1; //初始化时出口e无下一个可走方块
Push(st, e);
mg[xi][yi] = -1; //将入口入栈后即表示此处不可再走
while (!StackEmpty(st))
{
//2.若有一条可输出路径，则打印
//获取栈顶元素
GetTop(st, e);
i = e.i; j = e.j; di = e.di;
//若取出的栈顶元素为迷宫的一条路径，则进行输出
if (i == xo && j == yo)
{
puts("找到一条迷宫路径如下");
k = 0;
while (!StackEmpty(st))
{
Pop(st, e); //出栈栈顶元素
path[k++] = e; //将从栈顶取出的迷宫方块依此放入path路径中
}
//逆序输出路径
while (k >= 1)
{
k--;
printf("\t(%d,%d)", path[k].i, path[k].j);
if ((k + 2) % 5 == 0)
printf("\n");
}
printf("\n");
DestroyStack(st);
return true;
}
//3.若还未找到可走方块，则继续往四周寻找
int i1 = 0, j1 = 0; //用于存放下一个可走方块的位置
find = false;
while (di < 4 && !find)
{
di++;
switch (di)
{
case 0:i1 = i - 1; j1 = j; break;
case 1:i1 = i; j1 = j + 1; break;
case 2:i1 = i + 1; j1 = j; break;
case 3:i1 = i; j1 = j - 1; break;
}
if (mg[i1][j1] == 0) find = true;
}
//4.判断栈中方块是否可走
if (find) { //若当前方块可走
st->data[st->top].di = di;
e.i = i1; e.j = j1; e.di = -1;
Push(st, e);
mg[i1][j1] = -1;
}
else { //若当前方块不可走
Pop(st, e); //将当前方块出栈
mg[e.i][e.j] = 0; //将当前方块的位置复原，供其他路径使用
}
}
//若栈出空了还是没有找到一条合适的路径，则返回false
DestroyStack(st);
return false;
}
int main(void)
{
if (!MyPath(1, 1, M, N))
{
puts("该迷宫问题没有解");
}
return 1;
}
- 从运行结果和路径展示来看，虽然是实现了一条路径的寻找，但是我们很明显可以看出这条路径并不是从入口到出口的最短路径，即不是最优解，那我们要如何是实现这个最优解呢？
- 接下来就轮到队列登场了:confetti_ball:
🌳队列实现
🌼优先分析
对于队列，我们都不陌生，它是一个先进先出【FIFO】的数据结构
- 上面我们有提到堆栈来寻找这条路径，但是堆栈的话在寻找方块是找到一个可走的方块就往下走了，完全没有考虑最短路径的这方面；但是如果我们使用队列的话，就可以将所有可走的方块都走一遍，去寻找所有的可能性，这也为找到一条最短路径做了很好的铺垫
- 那使用队列去找一条最短路径使用的是什么原理呢，其实就是==当前方块，它回去四周寻找它觉得可走的方块，然后呢，那些相邻可走的方块所指向的前驱方块均为当前方块==
- 以下图示就是队列在迷宫中寻找路径的原理:point_down:
🌼结构的设立与框架体系
明白了队列在迷宫中如何去寻找一条最短路径的底层原理，接下来我们就要往代码层面去分析，首先就是将封装的结构体声明出来
typedef struct
{
int i, j; //方块的位置
int pre; //本路径中上一个方块在队列中的下标
}Box; //方块类型
typedef struct Queue {
Box data[MAX];
int front, rear; //队头、队尾指针
}QuType; //顺序队
- 我们来看一下上述代码，首先是一样的方块类型，位置必须要有，然后和队列不同的是，这里是一个叫pre的成员，指的就是==本路径中上一个方块在队列中的下标==，定义这个成员其实就是为了在后面沿着出口找上一个路径的时候可以通过pre去很快地寻找
- 接下去是一个队列的声明，可以看到，我们没有用链式队也没有用循环队，而是使用了一个最基本的顺序队去实现，因为我们在找到出口的时候需要利用队列中的所有方块查找一条迷宫路径。但如果我们采用环形队列的话，那出队的方块可能就会被新进队的方块覆盖，从而无法求出迷宫路径
- 既然是队列，那就一定有队头和队尾指针，这在后面的实现中也是很重要的东西
- 还有一点要注意的是，这里我们在定义顺序队的时候，要有足够存储空间，因为我们每次是要去求出所有可走的方块，所以就会导致队列中会放进很多的方块，万一容量不够的话也会导致内存泄漏，==当然你也可以在定义顺序队实现的时候，在入队的地方进行一个动态规划==
了解了队列结构该如何去设计，接下来我们要去构思整个程序该如何去实现
- 首先第一步还是一样，要讲入口先进队，以及进行一个初始化还要声明需要用到的变量
- 第二步去判断此时是否找到出口，若是找到了出口，则进行打印输出
- 第三步我们要去进行一个搜索，寻找当前方块的四周有哪些方块是可以走的，这里要注意，需要将每一个可走的方块都入队
🌼代码的实现与逻辑分析
了解了队列的寻找路径的底层实现，对总体的设计框架也有了一个很清晰的认识，接下去我们就需要专注于去实现这些代码
- 一样，我们需要先有一个迷宫路径
int mg[M + 2][N + 2] =
{ {1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
- 初始化的操作与栈一致，就是不需要有一条路径专门去存放，我们将其专门封装为一个打印的函数，还有一点就是这个e.pre = -1，因为入口比较特殊，它的前面没有任何的方块，所以为-1
bool mgpath(int xi, int yi, int xo, int yo)
{ //入口（xi,yi） 出口（xo,yo）
Box e; //定义一个方块用以存储走过的位置 - 需要操作的方块
int i, j, i1, j1, di; //i,j表示找到的结果方块的位置
//i1,j1表示还需遍历的四周其他方块的位置
//初始化队列
QuType* q;
InitQueue(q);
//初始化入口方块
e.i = xi;
e.j = yi;
e.pre = -1;
EnQueue(q, e); //入队
mg[e.i][e.j] = -1; //入口的索引值设置为-1
- 接下去就是本块最终要的路径打印，若是发现当前队头方块为出口，就要开始回溯打印路径了，我们将其单独封装为一个函数，需要传入的是当前方块以及前一方块的位置
while (!QueueEmpty(q))
{
//若找到迷宫的一条路径
DeQueue(q, e); //将当前队头的方块e出队，判断是否为出口
i = e.i;
j = e.j;
if (i == xo && j == yo) //若不为出口，不进判断，不打印
{
print(q, q->front); //反推出一条对应的迷宫路径并输出
DestroyQueue(q);
return true;
//找到一条路径，则销毁队列，返回true
}
- 我们来重点看一下路径是如何被打印出来的
- 首先要去获取这个前驱方块，通过一个循环，一直往前去寻找方块，也就是通过pre去获取上一个方块的位置，这里要尤其注意的是，我们要先记录下当前方块的前一个方块的位置，==因为如果不将其记录的话，在前一个方块再去寻找它的前一个方块的时候，前一个方块的位置就会丢失==，最要要将遍历过的方块设为-1，表示此方块不能再被行走
- 然后我们看到下一个while循环，当这个当前方块的上一个方块为-1时，也就是我们在初始化的时候所置的e.pre = -1，这是就构成了一条正向的路径，我们只需要去统计个数然后按顺序输出即可
- 讲一下你们会有的一个疑惑，为什么返回找路径的时候要用do…while()，但是输出路径的时候用的是while()，这是因为一个方块它一定是由一个前驱方块所走出来的，它一定是有且仅有一个前驱结点，嗯。。不小心说成结点了，其实这个的话和后面章节的【树和二叉树】有点关系，涉及到父亲节点和孩子结点之间的关系
- 但是对于输出路径就不一定了，需要先判断一下这个k是否小于MAX最大值，而且是否在向上寻找的时候构成了一条正向路径
void print(QuType* qu, int front)
{
int k = front, j, ns = 0;
cout << endl;
do
{ //反向找到最短路径
j = k;
k = qu->data[k].pre;
qu->data[j].pre = -1; //将该路径上方块的pre成员设置为-1
} while (k != 0);
cout << "有一条迷宫路径如下：" << endl;
k = 0;
while (k < MAX)
{
if (qu->data[k].pre == -1)
{ //正向搜索到pre为-1的方块，即构成正向的路径
ns++;
cout << "\t(" << qu->data[k].i <<"," << qu->data[k].j <<")";
if (ns % 5 == 0) //每输出五个方块换行
cout << endl;
}
k++;
}
cout << endl;
}
- 这是按照回溯去寻找到一个过程，供大家参考📚
- 最后一个就是去判断若是第一次没有找到出口，则要怎么去寻找可走的方块
- 这里要非常注意的一点是它是处于一个循环中的，也就每个方块在寻找下一个可走方块的时候一定会寻找4次，若全部都可走，那么会将他们全部入队
- 这里值得关注的一点就是==e.pre = q->front==，将当前方块与前一个方块形成一个链接的关系，方便后续的搜寻
//若找到的不是出口，则继续遍历相邻的其他方块
for (di = 0; di < 4; ++di)
{
switch (di)
{
case 0: i1 = i - 1; j1 = j; break;
case 1: i1 = i; j1 = j + 1; break;
case 2: i1 = i + 1; j1 = j; break;
case 3: i1 = i; j1 = j - 1; break;
}
if (mg[i1][j1] == 0) //如果发现方块是可以走的
{
e.i = i1;
e.j = j1; //把当前方块的坐标给到e
e.pre = q->front; //将此前方块与前一个方块相连
EnQueue(q, e);
mg[i1][j1] = -1;
}
}
🌼整体代码展示
我们先展示一下整体的代码，有些小伙伴等不及了，下一版块再去对比分析
#pragma once
#pragma once
#include <stdio.h>
#include <malloc.h>
#define MAX 50
#define M 8
#define N 8
typedef struct
{
int i, j; //方块的位置
int pre; //本路径中上一个方块在队列中的下标
}Box; //方块类型
typedef struct Queue {
Box data[MAX];
int front, rear; //队头、队尾指针
}QuType; //顺序队
/*初始化队列*/
void InitQueue(QuType*& q)
{
q = (QuType*)malloc(sizeof(QuType));
q->front = q->rear = -1;
}
/*摧毁队列*/
void DestroyQueue(QuType*& q)
{
free(q);
}
/*判断队列是否为空*/
bool QueueEmpty(QuType* q)
{
return q->front == q->rear;
}
/*入队*/
bool EnQueue(QuType*& q, Box e)
{
if (q->rear == MAX - 1)
return false;
else
{
q->rear++;
q->data[q->rear] = e;
return true;
}
}
/*出队*/
bool DeQueue(QuType*& q, Box& e)
{
if (q->front == q->rear) //表示队列为空
return false;
else
{
q->front++;
e = q->data[q->front];
return true;
}
}
/*求队列长度*/
int QuLength(QuType* q)
{
return ((q->rear - q->front) + MAX) % MAX;
}
/*显示队列*/
void DisplayQueue(QuType* q)
{
int len = QuLength(q);
Box e;
for (int i = 0; i < len; ++i)
{
DeQueue(q, e);
printf("%d ", e);
}
printf("\n");
}
#include <iostream>
#include "listQ.hpp"
#include <algorithm>
using namespace std;
//需要利用已经出队的元素
int mg[M + 2][N + 2] =
{ {1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
void print(QuType* qu, int front)
{
int k = front, j, ns = 0;
cout << endl;
do
{ //反向找到最短路径
j = k;
k = qu->data[k].pre;
qu->data[j].pre = -1; //将该路径上方块的pre成员设置为-1
} while (k != 0);
cout << "有一条迷宫路径如下：" << endl;
k = 0;
while (k < MAX)
{
if (qu->data[k].pre == -1)
{ //正向搜索到pre为-1的方块，即构成正向的路径
ns++;
cout << "\t(" << qu->data[k].i <<"," << qu->data[k].j <<")";
if (ns % 5 == 0) //每输出五个方块换行
cout << endl;
}
k++;
}
cout << endl;
}
bool mgpath(int xi, int yi, int xo, int yo)
{ //入口（xi,yi） 出口（xo,yo）
Box e; //定义一个方块用以存储走过的位置 - 需要操作的方块
int i, j, i1, j1, di; //i,j表示找到的结果方块的位置
//i1,j1表示还需遍历的四周其他方块的位置
//初始化队列
QuType* q;
InitQueue(q);
//初始化入口方块
e.i = xi;
e.j = yi;
e.pre = -1;
EnQueue(q, e); //入队
mg[e.i][e.j] = -1; //入口的索引值设置为-1
while (!QueueEmpty(q))
{
//若找到迷宫的一条路径
DeQueue(q, e); //将当前队头的方块e出队，判断是否为出口
i = e.i;
j = e.j;
if (i == xo && j == yo) //若不为出口，不进判断，不打印
{
print(q, q->front); //反推出一条对应的迷宫路径并输出
DestroyQueue(q);
return true;
//找到一条路径，则销毁队列，返回true
}
//若找到的不是出口，则继续遍历相邻的其他方块
for (di = 0; di < 4; ++di)
{
switch (di)
{
case 0: i1 = i - 1; j1 = j; break;
case 1: i1 = i; j1 = j + 1; break;
case 2: i1 = i + 1; j1 = j; break;
case 3: i1 = i; j1 = j - 1; break;
}
if (mg[i1][j1] == 0) //如果发现方块是可以走的
{
e.i = i1;
e.j = j1; //把当前方块的坐标给到e
e.pre = q->front; //将此前方块与前一个方块相连
EnQueue(q, e);
mg[i1][j1] = -1;
}
}
}
DestroyQueue(q);
return false; //若遍历结束还是没找到一条路径，则销毁队列，返回false
}
int main(void)
{
if (!mgpath(1, 1, M, N))
cout << "该迷宫问题没有解" << endl;
return 1;
}
🌳对比分析透显人生意义
堆栈寻找的路径
队列寻找的路径
- 通过两张的测试结果图，我们可以看出用队列去查找一条迷宫路径方面，要比堆栈来的更优
- 上面说过，堆栈在搜索可走方块的时候，当搜索到一个可走方块，就立即走下去了，像一匹横冲直撞的野马，要的东西不多，只要对了就行
- 但是对于队列来说，它回去搜索所有可走的方块然后将它们全部入队，这也会导致队列中的结点会渐渐越来越多，像是一个贪心的人，想要将可以拥有的都拥入自己的怀中，然后再去挑选出自己最想要、最喜欢的那一样，这其实就是人性的贪婪
- 但对于求解最短路径来说，其实就是要==贪==，有些时候不贪的话就达成不了自己的目的，就想【图】章节的迪杰斯特拉(Dijkstra)最短路径，也是属于贪心算法的一种:walking:
其实我们的人生何尝不是在走迷宫，一直在寻找一条自己认为对的出路，但又时常迷失方向，原因就是大家都想要走捷径，都希望通过任何方式去寻找一条通往成功的最短路径，最终虽赢得了世界，但却失去了自己原本最宝贵的东西——❤初心❤
🌳总结与提炼
本文我们重点讲解了如何通过堆栈和队列去查找一条迷宫的路径问题，也分析两种数据结构的底层是原理，分析了他们在实现一条路径的时候各有优劣，视具体场景而定
以上就是本文的所有内容，如有疑问请于评论区留言或者私信我，感谢您的观看:four_leaf_clover:
【版权声明】本文为华为云社区用户原创内容，未经允许不得转载，如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）