校招经典笔试题----迷宫问题(1)--C语言版-创新互联
目录
1. 题目描述
2. 核心算法
2.1 回溯算法
2.2 深度优先遍历
3. 题目详解
3.1 整体思路
3.2 思路详解
3.2.1 动态开辟二维数组
3.2.2 数据的输入
3.2.3 递归函数的实现
3.2.4 倒数据并输出
4. 完整代码
4.1 Stack.h
4.2 Stack.c
4.3 maze.c
5. 非常重要
先来看一张形象的图片唤起儿时的记忆
1. 题目描述这里是原题的链接：迷宫问题__牛客网迷宫问题
https://www.nowcoder.com/questionTerminal/cf24906056f4488c9ddb132f317e03bc
题目给定一个二维数组，并输入数据进行填充，数字1代表墙，数字0代表通路，只能上下左右走，不能斜着走。要求从左上角走到右下角，输入保证只有一条到终点的路。
2. 核心算法 2.1 回溯算法该算法在本题中的体现就是当到达一个上下左右都走不通的坐标时，需要倒退回去，重新寻找路线。是不是就立刻想到了递归。
推荐题库：力扣
2.2 深度优先遍历
该算法在本题中的体现就是，选择一条路一直走，直到走不通，或者找到出口。与之对立的是广度优先遍历，本题用此算法比较复杂不建议使用。
3. 题目详解 3.1 整体思路推荐题库：力扣
1）：通过题目输入的几行几列的数组，在堆上动态开辟一个二维数组。
2）：通过两层for循环完成对迷宫数据的输入。
3）：书写一个递归函数，来寻找到达终点的路径，并将结果存储到数据结构----栈中。
4）：再次创建一个栈将存放好的路径倒过来，最后输出数据即可。
3.2 思路详解 3.2.1 动态开辟二维数组我们都知道二维数组在传参时，如果写成指针的形式是二级指针。那么，我们在堆上开辟空间时，取的变量类型就得是二级指针。那他的每一个元素就是一个一级指针（一维数组的数组名就是个一级指针嘛），每一个元素都是一个一级指针，才能用来接收在堆上开辟的连续的整型的空间。
//二维数组的行指针，N代表几行
int** maze = (int**)malloc(sizeof(int*)*N);
//二维数组的列指针
int i = 0;
for (i = 0; i< N; i++)
{
//M代表几列
maze[i] = (int*)malloc(sizeof(int) * M);
}这部分比较简单，不做分析。
//迷宫的初始化，N行M列的数组
int N, M;
scanf("%d %d", &N, &M);
//数据输入
int k, m;
for (k = 0; k< N; k++)
{
for (m = 0; m< M; m++)
{
scanf("%d", &maze[k][m]);
}
}1）：既然是递归函数那么一定有结束条件，显然就是当找到终点坐标（N-1，M-1）就结束啦。
2）：每走过一个坐标我们就要记录此坐标，进入递归函数就需要将该坐标入栈（栈中的每一个元素不是int，而是一个结构体，结构体里面存放坐标的行row，坐标的列col）。
3）：走过的位置在递归的过程中显然不能够再走，不然就会死递归，类比扫雷的一次展开一片无雷的区域。我们通过改变迷宫数组的值（令走过的坐标值为2）来实现目的。
4）：接下来我们需要对当前坐标的下一个坐标（上，下，左，右）进行判断，是否能往该方向（上，下，左，右）走，能走的条件：下一个坐标（上，下，左，右）的下标不越界，数值只能为0（1代表墙，2代表走过的位置）。如果上下左右都走不通，代表走到了死路，我们需要回退，找到新的路线，同时回退一步，栈中就需要出一个元素，以此来代表改路线行不通。更新新的路线。
5）：找路线的函数递归完成那么栈中就得到了正确的路线啦。
//判断此坐标是否能走
bool IsPath(int** maze, int N, int M, Pos cur)
{
if (cur.row >= 0
&& cur.row< N
&& cur.col >= 0
&& cur.col< M
&& maze[cur.row][cur.col] == 0)
{
return true;
}
return false;
}
//寻找通路的函数，参数1：迷宫的二维数组，参数2：迷宫的行，参数3：迷宫的列，参数4：存放坐标的结构体
bool GetMazePath(int** maze, int N, int M, Pos cur)
{
//入栈，记录路径
StackPush(&path, cur);
//递归的结束条件----到达终点
if (cur.row == N - 1 && cur.col == M - 1)
{
return true;
}
//定义结构体，表示下一个要走的位置
Pos next;
//进这个函数就表示此位置已经走过，改变该坐标的值，防止出现死递归
maze[cur.row][cur.col] = 2;
//定义一个结构体用来表示下一个将要走的坐标
//向上走，列不变行减一
next = cur;
next.row -= 1;
//判断该点是否能走
if (IsPath(maze, N, M, next))
{
//如果能返回true那么肯定找到了终点，逐层返回
if (GetMazePath(maze, N, M, next))
{
return true;
}
}
//向下走，列不变行加一
next = cur;
next.row += 1;
//判断该点是否能走
if (IsPath(maze, N, M, next))
{
//如果能返回true那么肯定找到了终点，逐层返回
if (GetMazePath(maze, N, M, next))
{
return true;
}
}
//向左走，行不变列减一
next = cur;
next.col -= 1;
//判断该点是否能走
if (IsPath(maze, N, M, next))
{
//如果能返回true那么肯定找到了终点，逐层返回
if (GetMazePath(maze, N, M, next))
{
return true;
}
}
//向右走，行不变列加一
next = cur;
next.col += 1;
//判断该点是否能走
if (IsPath(maze, N, M, next))
{
//如果能返回true那么肯定找到了终点，逐层返回
if (GetMazePath(maze, N, M, next))
{
return true;
}
}
//走到这里代表此坐标上下左右都走不通，开始回退
StackPop(&path);
//函数递归到此代表上下左右都走不通，返回false
return false;
}光看代码可能不好理解，大家可以尝试画出递归函数的展开图，以此来加深对递归的理解，亲测有效。
因为栈的特性，先进后出嘛，经过递归我们得到的数据不能直接输出，是反着的嘛。这时候我们创建一个新的栈，把原来的数据导入进去再打印输出即可。
#pragma once
#include#include
#include#include#include#include#define INIT_STACK_SIZE 4
//数据类型结构体，用来放坐标
typedef struct Position
{
int row;
int col;
}Pos;
typedef Pos ST_DATA_TYPE;
typedef struct Stack
{
ST_DATA_TYPE* data;
int size;
int capacity;
} ST;
void StackInit(ST* st);
void StackDestory(ST* st);
void StackPush(ST* st, ST_DATA_TYPE x);
void StackPop(ST* st);
ST_DATA_TYPE StackTop(ST* st);
void StackSize(ST* st);
bool StackEmpty(ST* st); #define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"
void StackInit(ST* st)
{
ST_DATA_TYPE* newlist = (ST_DATA_TYPE*)malloc(sizeof(ST_DATA_TYPE) * INIT_STACK_SIZE);
if (newlist != NULL)
{
st->data = newlist;
st->capacity = INIT_STACK_SIZE;
st->size = 0;
}
}
void StackDestory(ST* st)
{
free(st->data);
st->data = NULL;
}
void StackPush(ST* st, ST_DATA_TYPE x)
{
if (st->size == st->capacity)
{
ST_DATA_TYPE* newlist = (ST_DATA_TYPE*)realloc(st->data, sizeof(ST_DATA_TYPE) * 2 * st->capacity);
if (newlist == NULL)
{
perror("StackPush");
}
else
{
st->data = newlist;
st->capacity *= 2;
}
}
st->data[st->size] = x;
st->size++;
}
void StackPop(ST* st)
{
assert(st->size >0);
st->size--;
}
ST_DATA_TYPE StackTop(ST* st)
{
assert(st);
assert(st->size);
return (st->data[st->size - 1]);
}
void StackSize(ST* st)
{
assert(st->data);
return st->size;
}
bool StackEmpty(ST* st)
{
assert(st->data);
return st->size == 0;
}#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"
//建立一个全局的栈，用来存储迷宫的路径
ST path;
//建立一个栈，用来翻转栈中的数据
ST rpath;
//翻转存储迷宫路径的栈，并且打印最终数据
void ShowPath(ST* path, ST* rpath)
{
while (!StackEmpty(path))
{
StackPush(rpath, StackTop(path));
StackPop(path);
}
while (!StackEmpty(rpath))
{
printf("(%d,%d)", StackTop(rpath).row,StackTop(rpath).col);
printf("\n");
StackPop(rpath);
}
}
//判断此路是否能继续往下走
bool IsPath(int** maze, int N, int M, Pos cur)
{
if (cur.row >= 0
&& cur.row< N
&& cur.col >= 0
&& cur.col< M
&& maze[cur.row][cur.col] == 0)
{
return true;
}
return false;
}
//寻找通路的函数，参数1：迷宫的二维数组，参数2：迷宫的行，参数3：迷宫的列，参数4：存放坐标的结构体
bool GetMazePath(int** maze, int N, int M, Pos cur)
{
//入栈，记录路径
StackPush(&path, cur);
//递归的结束条件----到达终点
if (cur.row == N - 1 && cur.col == M - 1)
{
return true;
}
//定义结构体，表示下一个要走的位置
Pos next;
//进这个函数就表示此位置已经走过，改变该坐标的值，防止出现死递归
maze[cur.row][cur.col] = 2;
//定义一个结构体用来表示下一个将要走的坐标
//向上走，列不变行减一
next = cur;
next.row -= 1;
//判断该点是否能走
if (IsPath(maze, N, M, next))
{
//如果能返回true那么肯定找到了终点，逐层返回
if (GetMazePath(maze, N, M, next))
{
return true;
}
}
//向下走，列不变行加一
next = cur;
next.row += 1;
//判断该点是否能走
if (IsPath(maze, N, M, next))
{
//如果能返回true那么肯定找到了终点，逐层返回
if (GetMazePath(maze, N, M, next))
{
return true;
}
}
//向左走，行不变列减一
next = cur;
next.col -= 1;
//判断该点是否能走
if (IsPath(maze, N, M, next))
{
//如果能返回true那么肯定找到了终点，逐层返回
if (GetMazePath(maze, N, M, next))
{
return true;
}
}
//向右走，行不变列加一
next = cur;
next.col += 1;
//判断该点是否能走
if (IsPath(maze, N, M, next))
{
//如果能返回true那么肯定找到了终点，逐层返回
if (GetMazePath(maze, N, M, next))
{
return true;
}
}
//走到这里代表此坐标上下左右都走不通，开始回退
StackPop(&path);
//函数递归到此代表上下左右都走不通，返回false
return false;
}
int main()
{
//迷宫的初始化，N行M列的数组
int N, M;
scanf("%d %d", &N, &M);
//动态开辟二维数组
//二维数组的行指针
int** maze = (int**)malloc(sizeof(int*)*N);
//二维数组的列指针
int i = 0;
for (i = 0; i< N; i++)
{
maze[i] = (int*)malloc(sizeof(int) * M);
}
int k, m;
for (k = 0; k< N; k++)
{
for (m = 0; m< M; m++)
{
scanf("%d", &maze[k][m]);
}
}
//入口的坐标
Pos cur = { 0,0 };
//初始化栈
StackInit(&path);
StackInit(&rpath);
//寻找通路的函数
if (GetMazePath(maze, N, M, cur))
{
printf("找到通路\n");
//打印最终的数据
ShowPath(&path, &rpath);
}
else
{
printf("没找到通路\n");
}
//释放空间
//释放每一行的空间
for (i = 0; i< N; i++)
{
free(maze[i]);
}
//释放列的指针
free(maze);
//销毁栈
StackDestory(&path);
StackDestory(&rpath);
return 0;
}那个递归的图可能看不清楚，需要清晰的图片请加我QQ：3310163044。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章题目：校招经典笔试题----迷宫问题(1)--C语言版-创新互联
标题路径：http://azwzsj.com/article/dicjch.html
