迷宫问题
迷宫问题详解（DFS)
前言：
希望在观看此片之前先去观看懒猫老师的视频，此篇是完全基于课程上的思想和方法来写的，这里直接给大家贴上地址：
https://www.bilibili.com/video/BV1oE41177wk/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=3daecc9000cbc58a3bc39bf941c4d208
对于迷宫算法 在这之前我们需要掌握二维数组，栈的相关知识，嵌套结构体，类等，从名字可以看出就是走迷宫的问题，那么我们就需要定义一个说明方向的二维数组，来说明我们该怎么移动，还需要定义一个数组，来记录我们每一次移动的时的坐标和方向，将每一个数组看成一个元素存储在我们的栈中，然后再逆序遍历栈中元素，就可以得到走出迷宫的正确路线，这只是大致的框架，具体里面的细节非常多，需要我们仔细思考调试来实现完整代码
由于具体代码较长，我们来分步骤分解这个问题：
具体过程
1.定义方向数组并使用嵌套结构体定义栈中元素
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int incX;
int incY;
}Direction;//分别表示横纵坐标的增加量
typedef struct {
int x;
int y;
int di;
}Box;//分别表示横纵坐标和移动方向
typedef struct Node{
Box data;
struct Node* next;
}Node;
int main() {
Direction direct[4];
direct[0].incX=0,direct[0].incY=1;//右
direct[1].incX=1,direct[1].incY=0;//下
direct[2].incX=0,direct[2].incY=-1;//左
direct[3].incX=-1,direct[3].incY=0;//上
return 0;
}
下面这张图就是我们direct数组初始化后的效果图：
2.实现栈的基本功能（基本功）
Pstack initsta() { // 初始化栈
Pstack s = (Pstack)malloc(sizeof(Stack));
Pnode phead = (Pnode)malloc(sizeof(Node));
s->pButtom = phead;
s->pTop = phead;
return s;
}
int push(Pstack s, box key) { // 压栈
Pnode pNew = (Pnode)malloc(sizeof(Node));
pNew->pNext = s->pTop;
s->pTop = pNew;
pNew->data.x = key.x;
pNew->data.y = key.y;
pNew->data.fx = key.fx;
return 0;
}
box pop(Pstack s) { // 出栈
box tmp;
if (s->pTop != s->pButtom) {
Pnode pTmp = s->pTop->pNext;
tmp.x = s->pTop->data.x;
tmp.y = s->pTop->data.y;
tmp.fx = s->pTop->data.fx;
free(s->pTop);
s->pTop = pTmp;
}
return tmp;
}
bool empty(Pstack s) { // 判断栈空
if (s->pTop == s->pButtom)
return true;
else
return false;
}
3.逆序输出栈中元素（难点之一）
这里给大家贴一个地址，一开始我也是一头雾水，看了别人的讲解才慢慢有了思路
https://blog.csdn.net/u012011079/article/details/113706223
这里面用到了栈与递归的思想，希望大家辅助别人的思想仔细体会，动手敲一下
// 递归逆序输出栈中元素
void recursiveReverse(Pstack s) {
if (empty(s)) {
return;
}
box tmp = pop(s);
recursiveReverse(s);
printf("(%d,%d)\n", tmp.x, tmp.y);
}
4. 拼凑函数与具体实现
前面基本上就是对于懒猫老师课上给的伪代码进行准备工作，具体是主函数findpath传入的每一个参数怎么实现，而下面则是对于课上代码的具体演示，可能会有很多改进的地方，对于上面的一些代码，我也是有很多不太明白或者遗忘的地方，也是看着别人的贴子一点一点对着理解然后又复制粘贴对于一些报错修改后，才形成了可以运行的代码，这里采用的是链栈，但希望大家对于下面的函数的每一步一定要弄明白，特别是对于这些if-else结构到底是怎么回事，一定要理解透彻，可以借助我的笔记，很详细！
bool findpath(int maze[][6], direction Dir[], Pstack s) {
box tmp; // 栈中操作的元素
int x, y, fx;
int row, col;
maze[1][1] = -1;
tmp.x = 1;
tmp.y = 1;
tmp.fx = -1;
push(s, tmp); // 迷宫入口进栈
while (!empty(s)) { // 栈不空, 循环
tmp = pop(s); // 出栈
x = tmp.x;
y = tmp.y;
fx = tmp.fx + 1;
while (fx < 4) {
row = x + Dir[fx].incx;
col = y + Dir[fx].incy;
if (maze[row][col] == 0) {
box newTmp;
newTmp.x = x;
newTmp.y = y;
newTmp.fx = fx;
push(s, newTmp);
x = row;
y = col;
maze[row][col] = -1;
if (row == M && col == N) {
box endTmp;
endTmp.x = row;
endTmp.y = col;
endTmp.fx = -1;
push(s, endTmp);
return true;
} else {
fx = 0;
}
} else {
fx++;
}
}
}
5.笔记
6.main函数
int main() {
int maze[M+2][N+2] = {
{1,1,1,1,1,1},
{1,0,0,0,0,1},
{1,1,0,1,1,1},
{1,0,0,0,1,1},
{1,1,1,0,0,1},
{1,1,1,1,1,1}
}; // 迷宫二维数组
direction Dir[4] = {
{0,1},
{1,0},
{0,-1},
{-1,0}
}; // 探测方向二维数组
Pstack s = initsta();
if (findpath(maze, Dir, s)) {
printf("find path\n");
recursiveReverse(s); // 使用递归函数逆序输出路径
} else {
printf("no path\n");
}
return 0;
}
结语
总的来说，这个算法比较难，不仅需要扎实的基础，还需要有一定的算法思维，对于各种问题的解决在懒猫老师的课程上都有，希望大家继续加油，整理不易，请多多点赞收藏关注，蟹蟹！等后续我彻底理解之后会在最后附上C++版本，而且事实上我认为这样会更简洁明了，易于理解
标签：tmp,return,fx,迷宫,direct,DFS,int,详解,pTop From： https://blog.csdn.net/2402_88307286/article/details/145098790