c语言|《校招大厂中等难度笔试题》纯C语言求解迷宫问题——进来测测你数据结构初阶学的怎么样（） c语言|数据结构|算法|数据结构

一、前言

?个人介绍：
大家好，我是李逢溪，是一个热爱计算机技术的非内卷者，酷爱游戏设计，未来希望从事游戏开发行业，欢迎大家与我一起交流进步?！
?今天我为大家带来了一道校招中大厂中等难度的笔试题，让大家感受一下校招大厂的笔试题难度是怎样的！

文章图片

二、迷宫求解问题

定义一个二维数组 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],既第一格是可以走的路。
（以上迷宫OJ题曾经是百度某一年的其中一个笔试题，迷宫问题本质就是一个图的遍历问题，从起点开始不断四个方向探索，直到走到出口。）
来源：牛客
??输入描述:
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述:
左上角到右下角的最短路径，格式如样例所示。
输入
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
输出
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
?大家对于这道题有什么思路吗？

文章图片

先梳理以下流程
?第一步：创建迷宫，获取迷宫地图
创建迷宫就是要我们建立一个二维数组，oj输入的时候要求输入数组的行和列。
创建方式一（使用变长数组）：

int n = 0; int m = 0; scanf("%d %d", &n, &m); int maze[n][m];

但要注意：

在 C89 中，必须使用常量表达式指明数组长度；也就是说，数组长度中不能包含变量，不管该变量有没有初始化。

而在 C99 中，可以使用变量指明数组长度。

由于vs2019不支持变长数组，为了调试，这里我们用另一种方式。

创建方式二（动态开辟二维数组）：
比如要创建5X5的二维数组
先开辟含有5个int* 的数组，5个int* 分别指向5个int类型的数组。
图解：

文章图片

参考代码：

//创建迷宫 int m = 0, n = 0; //m代表行，n代表列 scanf("%d %d", &m, &n); int** maze = (int**)malloc(sizeof(int*) * m); for (int i = 0; i < m; ++i) { maze[i] = (int*)malloc(sizeof(int) * n); } for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &maze[i][j]); } }

其中m代表行，n代表列。
但这样还不是很好，没有考虑多组输入的问题。
修改：

// 创建迷宫，获取迷宫地图 int m = 0, n = 0; while (scanf("%d %d", &m, &n) != EOF) { int** maze = (int**)malloc(sizeof(int*) * m); for (int i = 0; i < m; ++i) { maze[i] = (int*)malloc(sizeof(int) * n); } for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &maze[i][j]); } } }

为了最后防止内存泄露，我们提前写好释放堆取的操作。
参考代码：

// 销毁迷宫 for (int i = 0; i < m; ++i) { free(maze[i]); } free(maze);

之后的核心代码就是如何找到通路并且打印路径的问题了。

文章图片

文章图片

我们的起点是（0，0），然后需要探察周围4个位置，如果其中一个位置能走，就走那个位置。
第一次探测，发现只有下面的位置可走，那走下面那个位置。

文章图片

走到第二个位置时，发现上面和下面都可走，这里肯定不能让它往回走，因此在我们移动之前，我们需要把当前位置置为非0和非1的数值，这里我们置为2。

文章图片

前两个0只有一条路可走，但走到第三个0时，有了两条路，此时可向右也可向下走。
我们不需要控制到底走哪条路，当有一条路走不通时，回到上一个位置即可。
假设我们往下走，直到无路可走。

文章图片

此时我们无路可走，那么就得回到上一个位置。
具体怎么回到上一个位置，我们先不解释。
当回到上一个位置，发现还是无路可走，直到返回到从开始位置走了2步的位置。

文章图片

又开始探索寻找可出的路，如果此路不通，则放回到上一个位置，直到找到出口。
最后我们还得打印通路的路径，找到通路后，该如何打印呢？
这里我们可以使用栈来实现，每次移动之前，将当前位置入栈，如果往回走，就出栈。
总的思路就是：不断探索周围的四个方向，如果可走那就走，无路可走时就返回到上一个位置，直到找到出口。
逻辑流程参考代码：

int main() { int N = 0, M = 0; while(scanf("%d%d", &N, &M) != EOF) { // int a[n][m]; // 动态开辟二维数组 int** maze = (int**)malloc(sizeof(int*)*N); for(int i = 0; i < N; ++i) { maze[i] = (int*)malloc(sizeof(int)*M); }// 二维数组的输入 for(int i = 0 ; i < N; ++i) { for(int j = 0; j < M; ++j) { scanf("%d", &maze[i][j]); } }StackInit(&path); PT entry = {0, 0}; if(GetMazePath(maze, N, M, entry)) { //printf("找到通路\n"); PirntPath(&path); } else { printf("没有找到通路\n"); }StackDestory(&path); for(int i = 0; i < N; ++i) { free(maze[i]); } free(maze); maze = NULL; } return 0; }

现在开始实现核心接口吧！

// 默认[0,0]是入口，[m-1][n-1]是出口 bool GetMazePath(int** maze, int N, int M, PT cur)//m是行,n是列 { // 核心逻辑 }

在移动之前我们需要将当期位置入栈。
由于C语言没有栈，我们得自己实现一个顺序栈。（这里我们就不实现了，复制接口后然后调用）。
但要将栈的元素类型做一点修改，因为位置是由行和列构成的一个结构体类型。

typedef struct Postion { int row; int col; }PT;

typedef PT STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST;

当前位置入栈后，要把当前位置的值修改成2。

StackPush(&path, cur); PT next; maze[cur.row][cur.col] = 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; }

代码解释：
如果上面的位置能走，则将当前位置变为上面的位置坐标。
然后再次调用函数自身，以递归的写法求解。
如果能走通，则返回true。
这里并排的几个if的作用实际就是回到上一个位置。（回溯到上一个位置）。
上下左右都不能走，则将当前位置出栈。
最后尝试都不能走通，那么返回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; // 探测cur位置得上下左右四个方向 PT next; maze[cur.row][cur.col] = 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; }

递归走读：

文章图片

首先起点是（0，0），调用函数bool GetMazePath(）。将当前位置入栈并修改为2后。

// 上 next = cur; next.row -= 1; if(IsPass(maze, N, M, next)) { if(GetMazePath(maze, N, M, next)) return true; }

在探测上方的位置，发现上方不通，不执行if里的语句

// 下 next = cur; next.row += 1; if(IsPass(maze, N, M, next)) { if(GetMazePath(maze, N, M, next)) return true; }

探测下方时，发现下方位置可行，则将当前位置修改为下方坐标，以当前位置做参数调用自身，从宏观上看，相当于求解：从下方位置到出口是否有通路，如果有通路，就返回true。
没有通路，就看入口（0，0）的左边位置到出口和入口右边的位置到出口是否有通路，如果都没有则返回false。即入口到出口不存在通路。
整个函数的递归思想：
?写递归思路：
首先明确函数的作用，函数的作用是判断从某个位置到出口位置是否存在通路，如果存在，则返回true，不存在则返回false。
再明确我们要求解的是：入口位置（0，0）到出口位置是否存在通路。
转换一下：如果入口的上下左右有一个位置能够到出口位置存在通路，则函数返回true。
如果都不能到达，则返回false。
而要判断从入口上方的位置到出口是否存在通路，不就可以调用函数自身实现吗？
需要注意的是：我们要有一个递归的出口：如果移动到出口，则返回true。
最后如何实现用栈存通路的路径呢？
第一步：将当前位置入栈
第二步：如果上下左右都不能通，则出栈。
写完这个递归总感觉不太信任，这是因为我们还没有理解这整个调用的过程。
为了理解这个递归的调用过程，我们需要画图验证。
?验证思路：
以下递归思路图只画了回溯到分叉入口。

文章图片

最后我们还有一个函数没有完成

bool IsPass(int** maze, int N, int M, PT pos)

这个判断下一个位置是否可以移动的函数看下面的代码就能理解，就不赘述了。
参考代码：

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; } }

最后要求输出路径，即从头打印栈的元素，由于栈只能后进后出，你又得先打印第一个元素，将原栈倒置在另一个栈，然后打印倒置后的栈。
【c语言|《校招大厂中等难度笔试题》纯C语言求解迷宫问题——进来测测你数据结构初阶学的怎么样（）】参考代码：

// 输出栈里面的坐标路径 void PirntPath(Stack* ps) { // path数据倒到rPath Stack rPath; StackInit(&rPath); while(!StackEmpty(&path)) { StackPush(&rPath, StackTop(&path)); StackPop(&path); }while(!StackEmpty(&rPath)) { PT top = StackTop(&rPath); printf("(%d,%d)\n", top.row, top.col); StackPop(&rPath); }StackDestory(&rPath); }

因为我们知道这里的栈是数组实现的，其实也可以不要倒置，直接打印数组元素。

三、整个代码分享

// 输出栈里面的坐标路径 void PirntPath(Stack* ps) { // path数据倒到rPath Stack rPath; StackInit(&rPath); while(!StackEmpty(&path)) { StackPush(&rPath, StackTop(&path)); StackPop(&path); }while(!StackEmpty(&rPath)) { PT top = StackTop(&rPath); printf("(%d,%d)\n", top.row, top.col); StackPop(&rPath); }StackDestory(&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; // 探测cur位置得上下左右四个方向 PT next; maze[cur.row][cur.col] = 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 a[n][m]; // 动态开辟二维数组 int** maze = (int**)malloc(sizeof(int*)*N); for(int i = 0; i < N; ++i) { maze[i] = (int*)malloc(sizeof(int)*M); }// 二维数组的输入 for(int i = 0 ; i < N; ++i) { for(int j = 0; j < M; ++j) { scanf("%d", &maze[i][j]); } }StackInit(&path); PT entry = {0, 0}; if(GetMazePath(maze, N, M, entry)) { //printf("找到通路\n"); PirntPath(&path); } else { printf("没有找到通路\n"); }StackDestory(&path); for(int i = 0; i < N; ++i) { free(maze[i]); } free(maze); maze = NULL; } return 0; }