百度面试题——迷宫问题(超详细解析)
一、迷宫问题
定义一个二维数组 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]);
}
}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;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);//内存销毁
}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
}6. 整体代码
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
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;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-09-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
