- 前言
- 迷宫问题原题
- 简略理解题意
- 解题思路
- 具体解题过程
- 一、先还原迷宫
- 二、求迷宫通路
- 1）建造雏形 仅返回bool值
- 2）引入栈 实现题目要求
- 最终答案代码
前言
- 牛客网上的迷宫问题 没怎么看到c语言的解答版本 也是数据结构栈的一个实际应用场景，值得学习
- 本篇文章主要解题思路在 注释 上，跟着代码一步步下去，再结合注释，应该不是很难理解
迷宫问题原题 简略理解题意
顾名思义，在这个迷宫里 1代表墙壁 0代表通路
我们只能上下左右地走不能斜着
系统会输入这个迷宫的长宽 以及迷宫的内容
我们需要输出通过迷宫的路径
最后使用一个个坐标来表示走的路径
暴力地把所有方向遍历一边 上下左右
用栈来存储坐标最后打印出来
我们这里采用2来表示已经走过的路
这样探测的时候就不会往回走，陷入死循环
走一步测一步，先把迷宫还原了再接下去解题
这里运用到了c语言 动态开辟二维数组 的知识点
while (scanf(“%d%d”, &N, &M) != EOF) 可以应对多个迷宫
还原出来的结果：
#include二、求迷宫通路 1）建造雏形 仅返回bool值#include void printMaze(int** maze, int N, int M) { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { printf("%d ", maze[i][j]); } printf("n"); } printf("n"); } int main() { int N = 0, M = 0; while (scanf("%d%d", &N, &M) != EOF)//应对多个迷宫 { //动态开辟一个二维数组储存迷宫 //int maze[N][M];变长数组 int** maze = (int**)malloc(sizeof(int*) * N);//创建指针数组-N行 for (int i = 0; i < N; i++) { maze[i] = (int*)malloc(sizeof(int) * M);创建指针数组-M列 } //读取迷宫到 maze 里 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%d", &maze[i][j]); } } //打印迷宫测试 printMaze(maze, N, M); //销毁迷宫 for (int i = 0; i < N; i++) {//从内向外销毁，先销毁每一行，再销毁maze free(maze[i]); } free(maze); } return 0; }
跟着代码一步步往下看，一般的疑问注释都有解释
#include#include #include //坐标结构体 typedef struct pation { int row;//行 int col;//列 }PT; void printMaze(int** maze, int N, int M) { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { printf("%d ", maze[i][j]); } printf("n"); } printf("n"); } 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)//判断合法性（有没有超过边界）以及是否为通路 { return true; } else return false; } bool GetMazePath(int** maze, int N, int M, PT cur) { if (cur.row == N - 1 && cur.col == M - 1) { return true; } //探测上下左右方向的通路 PT next; maze[cur.row][cur.col] = 2;//每走一个坐标 标记为2 表示已走过 //上 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;//找到出口就不用继续探测了 } return false; } int main() { int N = 0, M = 0; while (scanf("%d%d", &N, &M) != EOF)//应对多个迷宫 { //动态开辟一个二维数组储存迷宫 //int maze[N][M];变长数组 int** maze = (int**)malloc(sizeof(int*) * N);//创建指针数组-N行 for (int i = 0; i < N; i++) { maze[i] = (int*)malloc(sizeof(int) * M);创建指针数组-M列 } //读取迷宫到 maze 里 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%d", &maze[i][j]); } } //打印迷宫测试 //printMaze(maze, N, M); PT entry = { 0,0 };//起点 if (GetMazePath(maze, N, M, entry))//测试是否有通路 printf("truen"); else printf("falsen"); //销毁迷宫 for (int i = 0; i < N; i++) {//从内向外销毁，先销毁每一行，再销毁maze free(maze[i]); } free(maze); } return 0; }
GetMazePath函数的递归调用图
帮助你理解 动图里看不太清具体代码 下面附上
大概意思就是：先从入口 [0, 0] 进入迷宫 ，依次探测上下左右是否是通路 ，一旦有通路就递归进去
进去后再判断，然后再次探测 持续到死路（上下左右均走不通 1 or 2）
到死路后返回false 开始回溯
这里假设回溯到了之前调用的地方，进行 if 判断，就会继续往下探测 找其他通路
如果还是没有其他通路就继续返回 flase 继续回溯
直到找到了一个有其他通路的点 然后继续递归调用…重复如此
最后就会找到 出口（在函数的最顶端就是判断出口的）
这里因为c语言没有自带栈，所以我们需要从外部 copy 一个栈来用 代码内用了分隔符来隔开栈
调用栈时注意把之前 typedef 的类型改成 PT 也就是这个题目要用的坐标结构体
在之前雏形的基础上引入了栈， 每次递归时都先把当前的坐标 存入 全局 栈 Path ，每次 回溯 前（返回false前）都把当前这个死路的坐标给 出栈
最后再把栈内的数据统一打印出来 就可以实现题目要求了
这里编写了一个新的接口 PrintPath 用于打印栈
由于栈是先入后出，后入先出的 所以我们需要把栈给颠倒过来 再打印
不然就变得和题目要求相反了 具体实现过程看接口代码
#include#include #include #include #include //坐标结构体 typedef struct pation { int row;//行 int col;//列 }PT; typedef PT STDataType; typedef struct Stack { STDataType* arr;//顺序表 int capacity;//容量 int top;//栈顶 }ST; void StackInit(ST* ps); void StackDestroy(ST* ps); void StackPush(ST* ps, STDataType x); void StackPop(ST* ps); STDataType StackTop(ST* ps); int StackSize(ST* ps); bool StackEmpty(ST* ps); const void checkcapacity(ST* ps) { assert(ps); if (ps->top == ps->capacity) { ps->capacity *= 2; STDataType* tmp = (STDataType*)realloc(ps->arr, ps->capacity * sizeof(STDataType)); if (tmp == NULL) { exit(-1); } ps->arr = tmp; } } void StackInit(ST* ps) { assert(ps); ps->arr = (STDataType*)malloc(3 * sizeof(STDataType)); if (ps->arr == NULL) { exit(-1); } ps->capacity = 3; ps->top = 0;//初始化时没有有效数据，这里记录下标为0处为栈顶 } void StackDestroy(ST* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->top = 0; ps->capacity = 0; } void StackPush(ST* ps, STDataType x) { assert(ps); checkcapacity(ps); ps->arr[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0);//确保不是空栈 栈空了删除没意义 ps->top--; } STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0);//确保不是空栈 栈空了找栈顶没意义 return ps->arr[ps->top - 1]; } int StackSize(ST* ps) { assert(ps); return ps->top; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } #include #include #include ST path;//定义一个全局变量 路径 void printMaze(int** maze, int N, int M) { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { printf("%d ", maze[i][j]); } printf("n"); } printf("n"); } void PrintPath(ST* ps) { //如果直接把栈的数据取出来，会发现是反的 //所以我们需要额外的一个栈帮助我们倒数据再打印 ST rpath; StackInit(&rpath); //倒数据 while (!StackEmpty(&path)) { StackPush(&rpath, StackTop(&path)); StackPop(&path); } //打印倒完后的数据 while (!StackEmpty(&rpath)) {//按格式打印 printf("(%d,%d)n", StackTop(&rpath).row, StackTop(&rpath).col); StackPop(&rpath); } StackDestroy(&rpath); } 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)//判断合法性以及是否为通路 { return true; } else return false; } bool GetMazePath(int** maze, int N, int M, PT cur) { StackPush(&path, cur);//存当前的坐标到栈里 if (cur.row == N - 1 && cur.col == M - 1) { return true; } //探测上下左右方向的通路 PT next; maze[cur.row][cur.col] = 2;//每走一个坐标 标记为2 表示已走过 //上 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; } int main() { int N = 0, M = 0; while (scanf("%d%d", &N, &M) != EOF)//应对多个迷宫 { //动态开辟一个二维数组储存迷宫 //int maze[N][M];变长数组 int** maze = (int**)malloc(sizeof(int*) * N);//创建指针数组-N行 for (int i = 0; i < N; i++) { maze[i] = (int*)malloc(sizeof(int) * M);创建指针数组-M列 } //读取迷宫到 maze 里 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%d", &maze[i][j]); } } //打印迷宫测试 //printMaze(maze, N, M); StackInit(&path);//初始化栈 PT entry = { 0,0 };//起点 if (GetMazePath(maze, N, M, entry)) { //printf("truen"); PrintPath(&path);//打印栈 } else printf("falsen"); StackDestroy(&path);//销毁栈 //销毁迷宫 for (int i = 0; i < N; i++) {//从内向外销毁，先销毁每一行，再销毁maze free(maze[i]); } free(maze); } return 0; }
到这里这道题就解完
#include#include #include #include #include //坐标结构体 typedef struct pation { int row;//行 int col;//列 }PT; typedef PT STDataType; typedef struct Stack { STDataType* arr;//顺序表 int capacity;//容量 int top;//栈顶 }ST; void StackInit(ST* ps); void StackDestroy(ST* ps); void StackPush(ST* ps, STDataType x); void StackPop(ST* ps); STDataType StackTop(ST* ps); int StackSize(ST* ps); bool StackEmpty(ST* ps); const void checkcapacity(ST* ps) { assert(ps); if (ps->top == ps->capacity) { ps->capacity *= 2; STDataType* tmp = (STDataType*)realloc(ps->arr, ps->capacity * sizeof(STDataType)); if (tmp == NULL) { exit(-1); } ps->arr = tmp; } } void StackInit(ST* ps) { assert(ps); ps->arr = (STDataType*)malloc(3 * sizeof(STDataType)); if (ps->arr == NULL) { exit(-1); } ps->capacity = 3; ps->top = 0;//初始化时没有有效数据，这里记录下标为0处为栈顶 } void StackDestroy(ST* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->top = 0; ps->capacity = 0; } void StackPush(ST* ps, STDataType x) { assert(ps); checkcapacity(ps); ps->arr[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0);//确保不是空栈 栈空了删除没意义 ps->top--; } STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0);//确保不是空栈 栈空了找栈顶没意义 return ps->arr[ps->top - 1]; } int StackSize(ST* ps) { assert(ps); return ps->top; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } #include #include #include ST path;//定义一个全局变量 路径 void printMaze(int** maze, int N, int M) { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { printf("%d ", maze[i][j]); } printf("n"); } printf("n"); } void PrintPath(ST* ps) { //如果直接把栈的数据取出来，会发现是反的 //所以我们需要额外的一个栈帮助我们倒数据再打印 ST rpath; StackInit(&rpath); //倒数据 while (!StackEmpty(&path)) { StackPush(&rpath, StackTop(&path)); StackPop(&path); } //打印倒完后的数据 while (!StackEmpty(&rpath)) {//按格式打印 printf("(%d,%d)n", StackTop(&rpath).row, StackTop(&rpath).col); StackPop(&rpath); } StackDestroy(&rpath); } 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)//判断合法性以及是否为通路 { return true; } else return false; } bool GetMazePath(int** maze, int N, int M, PT cur) { StackPush(&path, cur);//存当前的坐标到栈里 if (cur.row == N - 1 && cur.col == M - 1) { return true; } //探测上下左右方向的通路 PT next; maze[cur.row][cur.col] = 2;//每走一个坐标 标记为2 表示已走过 //上 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; } int main() { int N = 0, M = 0; while (scanf("%d%d", &N, &M) != EOF)//应对多个迷宫 { //动态开辟一个二维数组储存迷宫 //int maze[N][M];变长数组 int** maze = (int**)malloc(sizeof(int*) * N);//创建指针数组-N行 for (int i = 0; i < N; i++) { maze[i] = (int*)malloc(sizeof(int) * M);创建指针数组-M列 } //读取迷宫到 maze 里 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%d", &maze[i][j]); } } //打印迷宫测试 //printMaze(maze, N, M); StackInit(&path);//初始化栈 PT entry = { 0,0 };//起点 if (GetMazePath(maze, N, M, entry)) { //printf("truen"); PrintPath(&path);//打印栈 } else printf("falsen"); StackDestroy(&path);//销毁栈 //销毁迷宫 for (int i = 0; i < N; i++) {//从内向外销毁，先销毁每一行，再销毁maze free(maze[i]); } free(maze); } return 0; }
