DFS走迷宫（懒猫老师C++完整版）

2024-06-21 17:38
文章标签 完整版 dfs 懒猫 c++ 迷宫 老师

本文主要是介绍DFS走迷宫（懒猫老师C++完整版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

DFS走迷宫的C++完整版

  • 知识储备
    • 一：普通动态二维数组的构造
    • 二：栈的构造
    • 三：栈的逆序遍历
  • Main文件代码

该版本代码是配合 懒猫老师用DFS走迷宫视频 基于C++基础所写的完整版（实现了栈逆序遍历），适合小白系统性的学习和复习知识点，只要将下文.h和.cpp和main文件所展示的代码结合起来就是个完整的代码。

知识储备

一：普通动态二维数组的构造

  1. 二维数组中不同行的内存空间不一定连续
  2. 释放内存时，需要先释放各个元素指向的内存，最后释放指针数组名指向的内存(层层释放)
  3. 动态二维数组释放后还会有个数组名地址（指针）的字节符大小
  4. 求数组大小的函数的时候必须将数组引用传递！否则数组会退化为一个指针，无法正确的使用sizeof运算符求出数组所占内存空间大小

下面对动态创建二维数组举例

/** 动态创建 */
int **nums = new int*[10];		//申请了一个int*类型的10行空间
for(int i = 0; i < 10; i++)
{nums[i] = new int[5];		//每一行申请一个int类型的5列空间
}/** 释放空间 */
for(int i = 0; i < 10; i++)delete[] nums[i];		//原则就是层层释放
delete[] nums;

注意：静态二维数组必须是要给定行/列的，如下代码是错误示范

int M, N;
cin >> M, N;
int maze[M+2][N+2];		//这里会报错，因为这是静态数组
// M 和 N尽管你有输入，但是编译器在预编译时是看成变量的，也就是不定的二维数组

二：栈的构造

迷宫问题中构造栈，我通过创建类来实现，具体怎么构造我这就不详细说了（因为这是基本功），.h文件用来存放方法声明，.cpp文件用来实现方法
以下是.h文件的代码（我去掉了析构函数）

struct Direction	//构建结构体
{int incX, incY;
};

构建Direction结构体是为了后面构造个结构体数组，该行走方向只有上下左右，没有左上、右上之类的，所以才储存4个方向，该数组储存内容如下图，如incX = 0, incY = 1是为了向右行走（X是横向，Y是纵向）
在这里插入图片描述

struct Box	//将每个迷宫格子看成是一个结构体
{int x, y, di;//x和y分别代表迷宫格子的横纵坐标，di为当前的方向
};typedef struct Node		//这是栈节点
{Box data;struct Node* pNext;
}Node, *PNODE;class Stack
{private:PNODE pTop;PNODE pBottom;public:Stack();void initStack(Stack*);void pushStack(Stack*, Box); //将栈中的栈底元素返回并移除，用递归来实现栈逆序遍历的Box getElement(Stack&, Box&);void reverse(Stack&, Box&); void traverse(Stack*);void pop(Stack*, Box&);bool isEmpty(Stack*);
};

以下是.cpp文件代码

#include "Stack.h"
#include <iostream>
#include <stdlib.h>		//exit函数要用到
using namespace std;Stack::Stack()
{//ctor
}void Stack::initStack(Stack* pS)
{pS->pTop = new Node;if(nullptr == pS->pTop){cout << "动态内存分配失败！" << endl;exit(-1);}else{pS->pBottom = pS->pTop;pS->pTop->pNext = nullptr;}return;
}void Stack::pushStack(Stack* pS, Box temp) //temp是将一个结构体整体入栈
{PNODE pNew = new Node;pNew->data = temp;pNew->pNext = pS->pTop;pS->pTop = pNew;
}
/** 这里开始是逆序遍历栈的关键代码，等会详细讲解 */
Box Stack::getElement(Stack& s, Box& temp)
{s.pop(&s, temp);Box res = temp;if(s.isEmpty(&s)) return res;else{Box last = getElement(s, temp);s.pushStack(&s, res);return last;}
}void Stack::reverse(Stack& s, Box& temp)
{if(s.isEmpty(&s)) return;Box i  = getElement(s, temp);s.reverse(s, temp);s.pushStack(&s, i);
}
/****************************************/
void Stack::traverse(Stack* pS)
{PNODE p = pS->pTop;		//p是移动指针，在栈顶和栈底间上下移动的while(p != pS->pBottom){cout << "(" << p->data.x << ", " << p->data.y << ")" << endl;p = p->pNext;}cout << endl;return;
}void Stack::pop(Stack* pS, Box& temp)	//这里的temp一定要 采用引用
{if(isEmpty(pS)) return;else{PNODE r = pS->pTop;temp = r->data;pS->pTop = r->pNext;free(r);r = NULL;return;}
}bool Stack::isEmpty(Stack* pS)
{if(pS->pTop == pS->pBottom)return true;elsereturn false;
}

三：栈的逆序遍历

我这里提供一种递归的思路来实现，当然也可以直接在自己构建栈遍历的方法中改进。栈的逆序遍历不难实现，看图和代码自己尝试下就行。其实这个知识点，也有些题会单独拿出来考，万一你面试的时候遇上这问题呢？~

Box Stack::getElement(Stack& s, Box& temp)
{s.pop(&s, temp);	//这里的temp是引用的，会随变化而变化Box res = temp;		//这里的temp和上面的temp一样//递归结束条件：栈空的时候，返回栈最底下的单元if(s.isEmpty(&s)) return res; 	else{Box last = getElement(s, temp);		//一直递归s.pushStack(&s, res);return last;}
}

为了方便理解上面代码，请结合代码和下图来看
getElement程序步骤演示
这时我们只是把一个栈最底部的单元提出来了，那么怎么接着提取其他呢？那当然可以用递归实现，就可以成功的反转栈了（如下代码）

void Stack::reverse(Stack& s, Box& temp) //这里的temp也要用引用
{if(s.isEmpty(&s)) return;Box i  = getElement(s, temp);s.reverse(s, temp);s.pushStack(&s, i);
}

也是结合代码来看下图理解吧，这里递归的reverse和pushStack可能比较难理解，简单来说就是进行一次reverse就含有一个pushStack，进行两次reverse就含有两个pushStack····直到栈空，每次return（有很多次，取决于栈元素的个数）前都会执行pushStack
reverse程序结构

Main文件代码

#include <iostream>
#include "Stack.h"using namespace std;bool findPath(Stack& s, int M, int N)
{int **maze = new int*[M+2];		//动态构造二维数组for(int i = 0; i < 10; i++){maze[i] = new int[N+2];}for(int i = 0; i < M+2; i++){	//动态给定迷宫for(int j = 0; j < N+2; j++){if(i == 0 || i == M+1)maze[i][j] = 1;else if(j == 0 || j == N+1)maze[i][j] = 1;elsecin >> maze[i][j];}}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;Box temp;int x, y, di;      //当前正在处理的迷宫格子int line, col;    //迷宫格子预移方向后，下一格子的行坐标、列坐标maze[1][1] = -1;temp.x = 1;temp.y = 1;temp.di = -1;		//起始点直接设置为-1代表该格子已访问过了s.pushStack(&s, temp);while(!s.isEmpty(&s)){s.pop(&s, temp);	//这里对遇到走不通的格子进行回退时起到关键作用x = temp.x; y = temp.y; di = temp.di+1;while(di < 4){  //走不通时，四个方向都尝试一遍line = x + direct[di].incX;col = y + direct[di].incY;if(maze[line][col] == 0){	//代表 预走 的格子可以走temp.x = x; temp.y = y; temp.di = di;s.pushStack(&s, temp);x = line; y = col; maze[line][col] = -1;	//标为-1是为了表明该格子已经走过，回溯时不再处理if(x == M && y == N){s.reverse(s, temp);return true;   //迷宫有路}else di = 0;}else di++;}}return false;       //迷宫无路
}int main()
{int M, N;bool res;cout << "请输入迷宫数组行数和列数：";cin >> M >> N;Stack s;s.initStack(&s);res = findPath(s, M, N);cout << boolalpha << res << endl;	//将bool转换为true/false显示cout << endl;if(res)s.traverse(&s);elsecout << "你被困在迷宫中了，等着受死吧！" << endl;return 0;
}

  ------------------以上是懒猫老师自构Stack的版本--------------------
  我们都知道C++提供了STL库，那么我们为何不用自带的stack更方便简洁呢？所以为了方便大家用C++，决定在下面开源个用STL库里stack的代码版本，同样也是实现了栈逆序遍历。

#include <bits/stdc++.h>
using namespace std;struct Direction
{int incX, incY;
};struct Box
{int x, y, di;
};Box getElement(stack<Box>& s)
{Box res = s.top();s.pop();if(s.empty()) return res;else{Box last = getElement(s);s.push(res);return last;}
}void reverseStack(stack<Box>& s)
{if(s.empty()) return;Box i = getElement(s);reverseStack(s);s.push(i);
}bool findPath(stack<Box>& s, int M, int N)
{//动态构建二维数组 new 出来的空间不一定是连续的int** maze = new int*[M+2];for(int i = 0; i < N + 2; i++)maze[i] = new int[N+2];for(int i = 0; i < M+2; i++){for(int j = 0; j < N+2; j++){if(i == 0 || i == M+1)maze[i][j] = 1;else if(j == 0 || j == N+1)maze[i][j] = 1;else cin >> maze[i][j];}}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;Box temp;int x, y, di;       //当前处理的单元格int row, col;     //走迷宫下一该走的单元格maze[1][1] = -1;temp.x = 1;temp.y = 1;temp.di = -1;s.push(temp);while(!s.empty()){x = s.top().x;  y = s.top().y;  di = s.top().di + 1;s.pop();while(di < 4){row = x + direct[di].incX;  col = y + direct[di].incY;if(maze[row][col] == 0){temp.x = x;  temp.y = y;  temp.di = di;s.push(temp);x = row;  y = col;  maze[row][col] = -1;if(x == M && y == N){reverseStack(s);return true;}else di = 0;}else di++;}}return false;
}void traverse(stack<Box> s)
{while(!s.empty()){Box temp = s.top();s.pop();cout << "(" << temp.x << ", " << temp.y << ")" << endl;}return;
}int main()
{int M, N;bool res;cout << "请输入迷宫数组的行数和列数：";cin >> M >> N;stack<Box> s;res = findPath(s, M, N);cout << boolalpha << res << endl;cout << endl;if(res)traverse(s);elsecout << "你被困在迷宫中了" << endl;return 0;
}

Input
8 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0
  
Output
(1, 1)
(1, 2)
(2, 2)
(3, 2)
(3, 1)
(4, 1)
(5, 1)
(5, 2)
(5, 3)
(6, 3)
(6, 4)
(6, 5)
(7, 5)
(8, 5)
(8, 6)
(8, 7)
  
--------------------------------------------------------
2022年2月24号更新：
  算法竞赛的DFS走迷宫（自定义起始和结束点，打印出所有路径）
👉例题：点这里
⭐大致题意： 第一行输入n，m代表迷宫的行数、列数，接下来输入 n 行和 m 列迷宫(1 表示可以走，0 表示不可以走)，倒数第二行代表起始点，倒数第一行代表结束点。用 “→” 连接符表示方向连接

#include <bits/stdc++.h>
using namespace std;const int N = 30;int n, m;
int g[N][N], d[N][N];		//g为邻接矩阵存储图，d为记录该点是否已经走过
bool flag = false;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {-1, 0, 1, 0};
pair<int, int> start;			//起始点
pair<int, int> over;			//结束点
pair<int, int> after[N][N];		//记录该点往后走哪个点void dfs(int xx, int yy){if(xx == over.first && yy == over.second){int a = start.first, b = start.second;flag = true;cout << "(" << a << "," << b << ")->";while(1){auto t = after[a][b];a = t.first, b = t.second;if(a == over.first && b == over.second){cout << "(" << a << "," << b << ")" << endl;break;}else cout << "(" << a << "," << b << ")->";}}int x, y;for(int i = 0; i < 4; i++){x = xx + dx[i], y = yy + dy[i];if(x >= 1 && x <= n && y >= 1 && y <= m &&d[x][y] == -1 && g[x][y] == 1){d[x][y] = 1;after[xx][yy] = {x, y};		//记录往后走哪个点dfs(x, y);d[x][y] = -1;x = xx, y = yy;}}
}int main(){cin >> n >> m;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> g[i][j];cin >> start.first >> start.second;cin >> over.first >> over.second;memset(d, -1, sizeof d);d[start.first][start.second] = 1;dfs(start.first, start.second);if(!flag) cout << -1 << endl;return 0;
}

路漫漫其修远兮，吾将上下而求索

这篇关于DFS走迷宫（懒猫老师C++完整版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1081883。

相关文章

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

1.为什么要引入虚拟继承 虚拟继承是多重继承中特有的概念。虚拟基类是为解决多重继承而出现的。如:类D继承自类B1、B2，而类B1、B2都继承自类A，因此在类D中两次出现类A中的变量和函数。为了节省内存空间，可以将B1、B2对A的继承定义为虚拟继承，而A就成了虚拟基类。实现的代码如下： class A class B1:public virtual A; class B2:pu
阅读更多...
C++对象布局及多态实现探索之内存布局（整理的很多链接）

C++对象布局及多态实现探索之内存布局（整理的很多链接）

本文通过观察对象的内存布局，跟踪函数调用的汇编代码。分析了C++对象内存的布局情况，虚函数的执行方式，以及虚继承，等等 文章链接：http://dev.yesky.com/254/2191254.shtml      论C/C++函数间动态内存的传递 (2005-07-30)   当你涉及到C/C++的核心编程的时候，你会无止境地与内存管理打交道。 文章链接：http://dev.yesky
阅读更多...
C++的模板(八)：子系统

C++的模板(八)：子系统

平常所见的大部分模板代码，模板所传的参数类型，到了模板里面，或实例化为对象，或嵌入模板内部结构中，或在模板内又派生了子类。不管怎样，最终他们在模板内，直接或间接，都实例化成对象了。 但这不是唯一的用法。试想一下。如果在模板内限制调用参数类型的构造函数会发生什么?参数类的对象在模板内无法构造。他们只能从模板的成员函数传入。模板不保存这些对象或者只保存他们的指针。因为构造函数被分离，这些指针在模板外
阅读更多...
C++工程编译链接错误汇总VisualStudio

C++工程编译链接错误汇总VisualStudio

目录 一些小的知识点 make工具 可以使用windows下的事件查看器崩溃的地方 dumpbin工具查看dll是32位还是64位的 _MSC_VER .cc 和.cpp 【VC++目录中的包含目录】 vs 【C/C++常规中的附加包含目录】——头文件所在目录如何怎么添加，添加了以后搜索头文件就会到这些个路径下搜索了 include<> 和 include"" WinMain 和
阅读更多...
C/C++的编译和链接过程

C/C++的编译和链接过程

目录 从源文件生成可执行文件（书中第2章） 1.Preprocessing预处理——预处理器cpp 2.Compilation编译——编译器cll ps：vs中优化选项设置 3.Assembly汇编——汇编器as ps：vs中汇编输出文件设置 4.Linking链接——链接器ld 符号 模块，库 链接过程——链接器 链接过程 1.简单链接的例子 2.链接过程 3.地址和
阅读更多...
C++必修：模版的入门到实践

C++必修：模版的入门到实践

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 🎈🎈养成好习惯，先赞后看哦~🎈🎈 所属专栏：C++学习 贝蒂的主页：Betty’s blog 1. 泛型编程 首先让我们来思考一个问题，如何实现一个交换函数？ void swap(int& x, int& y){int tmp = x;x = y;y = tmp;} 相信大家很快就能写出上面这段代码，但是如果要求这个交换函数支持字符型
阅读更多...
C++入门01

C++入门01

1、.h和.cpp 源文件 (.cpp)源文件是C++程序的实际实现代码文件，其中包含了具体的函数和类的定义、实现以及其他相关的代码。主要特点如下：实现代码: 源文件中包含了函数、类的具体实现代码，用于实现程序的功能。编译单元: 源文件通常是一个编译单元，即单独编译的基本单位。每个源文件都会经过编译器的处理，生成对应的目标文件。包含头文件: 源文件可以通过#include指令引入头文件，以使
阅读更多...
C++面试八股文：std::deque用过吗？

C++面试八股文：std::deque用过吗？

100编程书屋_孔夫子旧书网 某日二师兄参加XXX科技公司的C++工程师开发岗位第26面： 面试官：deque用过吗？ 二师兄：说实话，很少用，基本没用过。 面试官：为什么？ 二师兄：因为使用它的场景很少，大部分需要性能、且需要自动扩容的时候使用vector，需要随机插入和删除的时候可以使用list。 面试官：那你知道STL中的stack是如何实现的吗？ 二师兄：默认情况下，stack使
阅读更多...
剑指offer（C++）--孩子们的游戏(圆圈中最后剩下的数)

剑指offer（C++）--孩子们的游戏(圆圈中最后剩下的数)

题目 每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去
阅读更多...
剑指offer（C++）--扑克牌顺子

剑指offer（C++）--扑克牌顺子

题目 LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为1
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2