-
百度面试题——迷宫问题(超详细解析)
一、迷宫问题
定义一个二维数组 N*M ，如 5 × 5 数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
数据范围：2<=nm<=10， 输入的内容只包含 0<=val<=1
1.思路
1.整体思想
迷宫问题的本质是图的遍历问题，从起点开始不断四个方向探索，直到走到出口，走的过程借助栈记录走过的路径，栈记录坐标有两个作用，一方面是记录走过的路径，一方面方便走到死路时进行回溯其他的道路。
2.如何区分走过的路与没有走过的路
当下标为(0,0)的数据找到下方的通路时，达到下标为(1,0)的数据后，才将下标为(0,0)的数据置为2
3.遇到死路时，如何回溯
只有上下左右 四个方向都不可以走时，才进行回溯，回溯到可以继续走的路口
2. 整体过程详细分析
采用的方向是 上 下 左 右 ，依次寻找，
注意在寻找的过程中每次都需要入栈
为了防止走到死路，进行回溯时无法区分走过的路与没有走过的路，所以将走过的路标记成 2
1.先将下标为(0，0)的数据入栈 ,图1的上面没有数据，去下寻找
2.寻找到了通路0，将下标为(1,0)的数据入栈****同时将走过的(0,0)标记成2
3.在下标为(1,0)时上面为1不能走，下面为0可以走
4.将下标为(2,0)的数据入栈，下标为(1,0)的数据置成2，同时判断上 下 左 都不可以走，只能走右边
5.到达下标(2,1)时发现时死路,此时就需要回溯到可以继续走的路口,当上下左右 都没有路可走时，就销毁栈顶元素，即将在栈中下标为(2,0)的数据销毁，同时回到原路。
6.注意此时的下标(1,0) 只能走左，右两个方向，因为前后方向已经递归回来了！, 走右方向达到下标(1,1)
7.先将下标(1,1)的数据入栈，在判断只有右边可以走。
8.将下标(1,2)的数据入栈，将下标(1,1)的数据置成2，在判断(1,2)的数据只有下边可以走。
9.此时的下标(2,2)为出口，再次通过递归出口的位置，此时下标为(0,0)的上下 左右方向都不能走，循环结束 。
此时的栈有先进后出的原则，所以为(2,2) ,(1,2),(1,1),(1,0),(0,0)2.动态开辟二维数组
假设 N为行 M为列
动态开辟了N个指针数组(数组中的每个元素都为一个指针)，
每个指针都指向了一块大小为M的空间
//动态开辟二维数组 int N=0;//行 int M=0;//列 //1.开辟N个指针数组 int** maze = (int**)malloc(sizeof(int*) * N); //2.开辟M个空间 int i = 0; for (i = 0; i < N; i++) { maze[i] = (int*)malloc(sizeof(int) * M); } int j = 0; for (i = 0; i < N; i++) { for (j = 0; j < M; j++) { scanf("%d", &maze[i][j]); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
3.内存销毁
1.一定不要直接free(maze) ,此时M个空间都是在每个指针指向后开辟的，并不会销毁。
2.所以要先将M个空间销毁，再将整体N个指针数组销毁//释放空间 //1.释放N个数组指针指向的空间 for (i = 0; i < N; i++) { free(maze[i]); } //2.将N个指针数组整体释放 free(maze); maze = NULL;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
4.用一个栈转移循环栈中的数据
如整体过程的分析，循环栈中为栈有先进后出的原则，所以为(2,2) ,(1,2),(1,1),(1,0),(0,0)
而我们要从入口的下标打印到出口的下标
所以采用在用一个栈，将循环栈中的数据传过来
此时的顺序为 (0,0),(1,0),(1,1),(1,2),(2,2)void printpath(ST* ps)//由于此时的path栈要打印出来会倒着出， //所以又重新创建了一个栈，将数据导进去 { ST rpath; stackinit(&rpath); while (!stackempty(&path)) { stackpush(&rpath, stacktop(&path)); stackpop(&path); } while (!stackempty(&rpath)) { PT top = stacktop(&rpath);//此时数据类型被改为PT printf("(%d,%d)", top.row, top.col); printf("\n"); stackpop(&rpath); } stackdestroy(&rpath);//内存销毁 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
5. getmazepath(maze, N, M, next)判断是否为真
若不判断该函数，在回溯时导致重复循环
回溯到下标为(1,0)的地方时，就会导致会重复向下的递归！，
从而无限循环下去ST path; bool getmazepath(int** maze, int N, int M, PT cur) { stackpush(&path, cur);//入栈 if (cur.row == N - 1 && cur.col == M - 1)//找到出口就返回真 { return true; } maze[cur.row][cur.col] = 2;//先将目前所处位置赋值为2 PT next; next = cur;//上 next.row -= 1; if (ispass(maze, N, M, next))//判断上的位置是否满足继续的条件 { if (getmazepath(maze, N, M, next))//满足条件就递归 { return true;//为了防止找到继续递归下去 返回真 } } next = cur;//下 next.row += 1; if (ispass(maze, N, M, next))//判断下的位置是否满足继续的条件 { if (getmazepath(maze, N, M, next))//满足条件就递归 { return true;//为了防止找到继续递归下去 返回真 } } next = cur;//左 next.col -= 1; if (ispass(maze, N, M, next))//判断左的位置是否满足继续的条件 { if (getmazepath(maze, N, M, next))//满足条件就递归 { return true;//为了防止找到继续递归下去 返回真 } } next = cur;//右 next.col += 1; if (ispass(maze, N, M, next))//判断右的位置是否满足继续的条件 { if (getmazepath(maze, N, M, next))//满足条件就递归 { return true;//为了防止找到继续递归下去 返回真 } } stackpop(&path); //如果上下左右都不满足就移除栈顶元素 return false;//如果上下左右都不满足就返回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
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
6. 整体代码
#define _CRT_SECURE_NO_WARNINGS #include#include #include #include typedef struct postion { int row;//行 int col;//列 }PT; / typedef PT datatype;//将数据类型改为结构体 typedef struct stack { datatype* a; int top; int capacity; }ST; void stackinit(ST* p); void stackpush(ST* p, datatype x); datatype stacktop(ST* p); void stackpop(ST* p); int stacksize(ST* p); bool stackempty(ST* p); void stackdestroy(ST* p); void stackinit(ST* p)//栈的初始化 { assert(p); p->a = NULL; p->top = 0; p->capacity = 0; } void stackpush(ST* p, datatype x)//入栈 { assert(p); if (p->top == p->capacity) { int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity; datatype* tmp = (datatype*)realloc(p->a, sizeof(datatype) * newcapacity); if (tmp != NULL) { p->a = tmp; p->capacity = newcapacity; } } p->a[p->top] = x; p->top++; } void stackpop(ST* p)//移除栈顶元素 { assert(p); assert(p->top > 0); p->top--; } datatype stacktop(ST* p)//出栈 { assert(p); assert(p->top > 0); return p->a[p->top - 1]; } bool stackempty(ST* p)//是否为空 { return p->top == 0; } int stacksize(ST* p)//栈中元素个数 { assert(p); return p->top; } void stackdestroy(ST* p)//内存销毁 { assert(p); free(p->a); p->a = NULL; p->top = 0; p->capacity = 0; } /// /// bool ispass(int** maze, int N, int M, PT pos) { if (pos.row >= 0 && pos.row < N && pos.col >= 0 && pos.col < M && maze[pos.row][pos.col] == 0) { //坐标不越界并且该处位置==0 return true; } return false; } ST path; bool getmazepath(int** maze, int N, int M, PT cur) { stackpush(&path, cur);//入栈 if (cur.row == N - 1 && cur.col == M - 1)//找到出口就返回真 { return true; } maze[cur.row][cur.col] = 2;//先将目前所处位置赋值为2 PT next; next = cur;//上 next.row -= 1; if (ispass(maze, N, M, next))//判断上的位置是否满足继续的条件 { if (getmazepath(maze, N, M, next))//满足条件就递归 { return true;//为了防止找到继续递归下去 返回真 } } next = cur;//下 next.row += 1; if (ispass(maze, N, M, next))//判断下的位置是否满足继续的条件 { if (getmazepath(maze, N, M, next))//满足条件就递归 { return true;//为了防止找到继续递归下去 返回真 } } next = cur;//左 next.col -= 1; if (ispass(maze, N, M, next))//判断左的位置是否满足继续的条件 { if (getmazepath(maze, N, M, next))//满足条件就递归 { return true;//为了防止找到继续递归下去 返回真 } } next = cur;//右 next.col += 1; if (ispass(maze, N, M, next))//判断右的位置是否满足继续的条件 { if (getmazepath(maze, N, M, next))//满足条件就递归 { return true;//为了防止找到继续递归下去 返回真 } } stackpop(&path); //如果上下左右都不满足就移除栈顶元素 return false;//如果上下左右都不满足就返回false } void printpath(ST* ps)//由于此时的path栈要打印出来会倒着出， //所以又重新创建了一个栈，将数据导进去 { ST rpath; stackinit(&rpath); while (!stackempty(&path)) { stackpush(&rpath, stacktop(&path)); stackpop(&path); } while (!stackempty(&rpath)) { PT top = stacktop(&rpath);//此时数据类型被改为PT printf("(%d,%d)", top.row, top.col); printf("\n"); stackpop(&rpath); } stackdestroy(&rpath);//内存销毁 } int main() { int N = 0; int M = 0; while (scanf("%d%d", &N, &M) != EOF)//多组输入 { //动态开辟二维数组 //1.开辟N个指针数组 int** maze = (int**)malloc(sizeof(int*) * N); //2.开辟M个空间 int i = 0; for (i = 0; i < N; i++) { maze[i] = (int*)malloc(sizeof(int) * M); } int j = 0; for (i = 0; i < N; i++) { for (j = 0; j < M; j++) { scanf("%d", &maze[i][j]); } } PT entry = { 0,0 }; stackinit(&path); if (getmazepath(maze, N, M, entry)) { printpath(&path);//输出通路的路径 } else { printf("没有通路\n"); } stackdestroy(&path); //释放空间 //1.释放N个数组指针指向的空间 for (i = 0; i < N; i++) { free(maze[i]); } //2.将N个指针数组整体释放 free(maze); maze = NULL; } 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
- 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
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
-
相关阅读:
npm报证书过期 certificate has expired问题（已解决）
jQuery 动画小练习
第11篇:ESP32vscode_platformio_idf框架helloworld点亮LED
C++中的继承（下）
【数据挖掘】生成模型和判别模型的区别及优缺点
长短期负荷预测（Matlab代码实现）
软件项目验收测试报告-软件项目验收流程
WalkMe的数字用户体验到底是啥
渤、黄海的潮汐特征
HarmonyOS 4.0 实况窗上线！支付宝实现医疗场景智能提醒
- 原文地址：https://blog.csdn.net/qq_62939852/article/details/126888727
