-
【算法】迷宫问题
前言
迷宫问题本质就是一个图的遍历问题，从起点开始不断四个方向探索，直到走到出口，走的过程中我们借助栈记录走过路径的坐标。
栈记录坐标有两方面的作用，一方面是记录走过的路径，一方面方便走到死路时进行回溯找其他的通路
1.迷宫问题求解
https://www.nowcoder.com/questionTerminal/cf24906056f4488c9ddb132f317e03bc
分析
1.此处1表示墙壁不能走，0表示可以走的路
2.(0，0)位置是起点(入口)， (N-1，M-1)是终点(出口)
3.所以思路就是从起点位置开始，向上下左右进行搜索。先判断位置是否合法，如果合法就递归往下继续搜索，不合法则走另一个位置进行搜索。如果四个方向都不合法，那么在保存坐标的容器删除当前位置的坐标。
4.因为是把最近的坐标弹出去，后进先出，所以使用的是栈保存坐标！
5.注意：由于最后输出的是从起点到终点的路径的坐标，栈自底往上才是答案，所以需要把栈的内容倒置过来
思路
0.由于我们要保存坐标的位置，这里可以使用pair，也可以自己定义一个结构体类型进行描述坐标
1.由于可能是循环输入例子，所以使用while(cin >> … )的方式输入N和M，然后开辟N*M的二维数组，输入数据。
2.从起点(0，0)位置开始调用递归函数GetMazePath找通路，题目已经说明了有唯一解！
3.首先要判断方向是否有效，有效才往那个方向走，只要GetMazePath中任意一个方向找到了通路就返回真，如果最后四个方向都不能走，就返回假
C语言如何开辟N*M的二维数组
//方式1： int maze[N][M] //C99不支持这种方式 //方式2：动态开辟二维数组 int** maze = (int**)malloc(sizeof(int*)*N) //数字共有N个元素，每个元素都是int*(指向一个动态的数组)，首元素的地址为int** for(int i = 0 ;i<N;i++) { maze[i] = (int*)malloc(sizeof(int)*M); } //释放：先释放一维数组，然后才能释放二维数组，否则就会导致内存泄漏 for(int i = 0;i<N;i++) { free(maze[i]); maze[i] = NULL; } free(maze); maze = NULL;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
分步骤求解
1.描述位置的结构体定义：
struct Postion { int row; int col; Postion(int x, int y) :row(x), col(y) {} };- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.定义一个全局的Stack，记录通路上的位置坐标
stack<Postion> Path; //记录通路的路径下标位置- 1
3.输出路径上的坐标的函数 (从起点到终点)
分析：由于Path栈中从栈底到栈顶才是题目要求的输出方式，所以我们需要把Path栈的内容进行倒置
void PrintPath() { //将Path栈中的内容倒置才是输出顺序 stack<Postion> rPath; while (!Path.empty()) { rPath.push(Path.top()); Path.pop(); } //按格式输出内容 while (!rPath.empty()) { Postion top = rPath.top(); printf("(%d,%d)\n", top.row, top.col); rPath.pop(); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
4.辅助函数：判断能否往pos位置的方向走
分析：只要保证pos的坐标不是越界的 &&pos位置的值是0（题目说明0是通路）那么就可以往该位置走
bool IsPass(vector<vector<int>>& vv, Postion& pos) { //获取迷宫的行和列 int N = vv.size(); int M = vv[0].size(); //pos位置合法&&pos位置的值是0才是通路，才是可以往pos位置走 //位置合法：位置的行>=0 && 位置的行=0 && 位置的列
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
5.主递归函数：从cur位置开始往四个方向进行搜索，找通路
分析：先把当前位置坐标放到路径栈当中，然后判断当前位置是不是出口，不是则要往四个方向进行探索！
注意1：我们需要把当前坐标位置的值改为非0值，表示当前位置已经走过了，不走回头路！否则就造成死递归了。当然也可以置为1，因为题目已经说明了1代表的是墙
注意2：往四个方向进行探索，先要检测该方向位置是否合法，只要任一方向找到了通路就可以返回了！因为答案唯一，所以先往哪个方向走的顺序都可以。如果四个方向都找不到通路，说明当前cur位置是无效的位置，需要回溯，把cur位置从栈中弹出。
bool GetMazePath(vector<vector<int>>& vv, Postion cur) { Path.push(cur);//先把当前位置坐标放到路径栈当中 int N = vv.size(); int M = vv[0].size(); if (cur.row == N - 1 && cur.col == M - 1)//判断是否走到出口 return true; vv[cur.row][cur.col] = 2;//把当前位置置成2,或者其它数字也可以，表示已经走过了！ //往四个方向进行探测，顺序任意，因为答案唯一 Postion nextUp{ cur.row - 1,cur.col }; Postion nextDown{ cur.row + 1, cur.col }; Postion nextLeft{ cur.row, cur.col - 1 }; Postion nextRight{cur.row, cur.col + 1}; //先判断能否往该方向走，如果能才往该方向进行下一步探索 //只要任一方向的探测走到出口就返回真 if (IsPass(vv, nextUp))//上 { if (GetMazePath(vv, nextUp)) return true; } if (IsPass(vv, nextDown))//下 { if (GetMazePath(vv, nextDown)) return true; } if (IsPass(vv, nextLeft))//左 { if (GetMazePath(vv, nextLeft)) return true; } if (IsPass(vv, nextRight))//右 { if (GetMazePath(vv, nextRight)) return true; } //来到这里，说明当前位置往四个方向走都不能得到通路 Path.pop();//当前位置不是路径上的位置 return false; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
6.主函数
分析：定义二维数组，然后输入数据，从起点(0,0)位置开始递归找通路，一定可以找到！然后输出路径上的坐标
int main() { int N, M; while (cin >> N >> M) { vector<vector<int>> maze(N, vector<int>(M)); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> maze[i][j]; Postion start{ 0,0 };//起点位置 if (GetMazePath(maze, start))//从起点位置开始探索找通路 { //找到通路了，输出路径 PrintPath(); } else { //没有通路，题目已经说明有唯一解，所以不可能走这里 cout << "没有通路" << endl; } } return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
代码
#include#include #include using namespace std; struct Postion { int row; int col; Postion(int x, int y) :row(x), col(y) {} }; stack<Postion> Path; //记录通路的路径下标位置 //输出路径上的坐标 起点->终点 void PrintPath() { //将Path栈中的内容倒置才是输出顺序 stack<Postion> rPath; while (!Path.empty()) { rPath.push(Path.top()); Path.pop(); } //按格式输出内容 while (!rPath.empty()) { Postion top = rPath.top(); printf("(%d,%d)\n", top.row, top.col); rPath.pop(); } } //判断能否往pos位置走 bool IsPass(vector<vector<int>>& vv, Postion& pos) { //获取迷宫的行和列 int N = vv.size(); int M = vv[0].size(); //pos位置合法&&pos位置的值是0才是通路，才是可以往pos位置走 //位置合法：位置的行>=0 && 位置的行 =0 && 位置的列
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
2.迷宫最短路径求解
https://www.nowcoder.com/questionTerminal/571cfbe764824f03b5c0bfd2eb0a8ddf
分析：
1.此题中多了体力的限制，向上移动消耗3体力，向下移动不消耗体力值，向左向右消耗1体力
2.并且此时位置的值是0代表的是到不了的位置(可以理解为墙)，位置的值是1表示通路
3.此时的入口是（0，0）位置，出口是（0，m-1）位置(右上角)
4.题目中要求选出体力消耗最小的路径 ，可以理解为求的是最短路径。此时可能没办法逃出迷宫，比如：体力值为负数
所以此处我们要准备两个栈：当前路径栈以及保存答案的栈，需要注意：并不是最短的路径就是答案，因为有体力的消耗，用体力值来过滤路径的合法性
如何找出最优解呢？
把所有的通路都找出来，然后比较，找出最短的路径。此时体力值也是限制选择路径的一个因素！
和上一个题的不同之处
1.此时1代表的是通路，0代表的是墙，所以能否往pos位置走的代码需要变动
if (pos.row >= 0 && pos.row < N && pos.col >= 0 &&pos.col< M&&vv[pos.row][pos.col] == 1)- 1
2.此处的输出格式也有变化
3.1：在GetMazePath函数当中，此时不再需要返回值了，因为此时要找最短的路径，找到了一条通路之后，还需要回溯继续找。
3.2：因为我们是先把当前位置置为2，所以最后四个方向走完回溯的时候，还需要"恢复现场"，把当前位置重新置为1
3.3：由于有体力值的消耗，所以我们要给GetMazePath函数多增加一个体力值的参数
3.4：此时的迷宫出口是右上角位置：(0，M-1)，如果当前位置是出口，那么就判断是否需要更新答案栈，条件为：体力值>=0 && 第一次进入栈为空 || 路径栈的大小 < 答案栈的大小
代码
#include#include #include using namespace std; struct Postion { int row; int col; Postion(int x, int y) :row(x), col(y) {} }; stack<Postion> Path; //记录通路的路径下标位置 stack<Postion> ansPath;//保存最短路径的栈 //输出路径上的坐标 起点->终点 void PrintPath() { //将ansPath栈中的内容倒置才是输出顺序 stack<Postion> rPath; while (!ansPath.empty()) { rPath.push(ansPath.top()); ansPath.pop(); } //按格式输出内容 最后一个坐标不加, 所以需要分成两部分打印 //当然也可以在内部判断rPath.size()是否为1，然后打印 while (rPath.size() > 1) { Postion top = rPath.top(); printf("[%d,%d],", top.row, top.col); rPath.pop(); } Postion top = rPath.top(); printf("[%d,%d]", top.row, top.col); rPath.pop(); } //判断能否往pos位置走 bool IsPass(vector<vector<int>>& vv, Postion& pos) { //获取迷宫的行和列 int N = vv.size(); int M = vv[0].size(); //pos位置合法&&pos位置的值是1才是通路，才是可以往pos位置走 //位置合法：位置的行>=0 && 位置的行 =0 && 位置的列
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
为什么这里最后可以直接恢复现场：vv[cur.row][cur.col] = 1呢，会不会把原来0的位置改成1？不会！因为如果vv[cur.row][cur.col] 是0的话，在if判断当中就不能往这个位置走，不会进入递归。所以凡是能进入GetMazePath函数的，其位置的值一定是1
另一种写法
要求的是体力消耗最小的路径，所以我们定义一个变量记录每条通路的体力值，然后比较，满足条件再更新
#includeusing namespace std; vector<pair<int, int>> gpath;//迷宫 int max_life = -1; //记录最大体力值 /* g:记录最终答案 visited:记录位置是否考察过(记得要恢复现场) x和y:当前位置的坐标 life：剩余体力值path： path：当前通路上的坐标集合 */ void dfs(vector<vector<int>> &g, vector<vector<int>> &visited, int x, int y, int life, vector<pair<int, int>> &path) { //越界 || 当前位置已经考察过了 || 体力值<0 就返回 if (x < 0 || x >= g.size() || y < 0 || y >= g[0].size() || g[x][y] == 0 ||visited[x][y] || life < 0) { return; } path.push_back(make_pair(x, y));//保存当前坐标 if (x == 0 && y == g[0].size() - 1) //迷宫出口 { if (life > max_life) //当前通路的体力值剩余更多 { gpath = path; max_life = life; } path.pop_back();//在当前通路上的坐标集合中弹出当前坐标，然后继续回溯找 return; } visited[x][y] = 1;//表示当前位置已经考察过了 //向四个位置进行搜索 dfs(g, visited, x - 1, y, life - 3, path);//上 dfs(g, visited, x + 1, y, life, path);//下 dfs(g, visited, x, y - 1, life - 1, path);//左 dfs(g, visited, x, y + 1, life - 1, path);//右 //在当前通路上的坐标集合中弹出当前坐标，然后继续回溯找，并且恢复现场 path.pop_back(); visited[x][y] = 0;//恢复现场，没考察过 } void show_path(vector<pair<int, int>> &path) { for (int i = 0; i < path.size(); ++i) { cout << '[' << path[i].first << ',' << path[i].second << ']'; if (i < path.size() - 1) { cout << ','; } } } int main() { int n, m, life; cin >> n >> m >> life; vector<vector<int>> grids(n, vector<int>(m)); vector<pair<int, int>> path; vector<vector<int>> visited(n, vector<int>(m, 0)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> grids[i][j]; } } dfs(grids, visited, 0, 0, life, path); if (!gpath.empty()) { show_path(gpath); } else { cout << "Can not escape!" << endl; } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
-
相关阅读:
如何使用python快速修改Excel表单中的大量数据
2022-09-20 第五组 张明敏 学习笔记
【Elasticsearch专栏 02】深入探索：Elasticsearch为什么使用倒排索引而不是正排索引
ESP32设备驱动-VCNL4010光传感器驱动
轻量通讯协议 --- MQTT
docker之常用指令
【共读】企业信息安全建设与运维指南（二）
保研笔记四 软件工程与计算卷二（8-12章）
Spark的数据输入、数据计算、数据输出
Oracle SQL执行计划操作（3）——物化视图相关操作
- 原文地址：https://blog.csdn.net/chuxinchangcun/article/details/133047656
