迷宫问题求解
https://www.nowcoder.com/questionTerminal/cf24906056f4488c9ddb132f317e03bc
以上迷宫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
题解
关于求解，肯定是先创建一个自身位置的结构体，由于c语言没有那么多库函数，所以我们只能自己写一个栈了
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef struct Postion
{
int row;
int col;
}PT;
typedef PT STDataType;
// 支持动态增长的栈
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack, ST;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
//满了 -> 扩容
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity *= 2;
}
}
ps->a[ps->top] = data;
ps->top++;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
///
栈写好之后，就开始进入求解路径了，首先得创建一个迷宫，获取迷宫地图，初始化自身位置，开始上下左右判断移动，为0表示无障碍，可以走；
这里就可以用递归来完成，走过的路要改成除0和1外的数（这里我用2来代替了），不然又会走重；当走到死路时，就需要往回走，回到一个有第二个方向可以走的位置，被称为回溯，还用到了栈的先进后出，所以用栈来记录路径是最好不够了；
Stack 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(Stack* ps)
{
//Path数据倒到rPath
Stack rPath;
StackInit(&rPath);
while (!StackEmpty(ps))
{
StackPush(&rPath, StackTop(ps));
StackPop(ps);
}
while (!StackEmpty(&rPath))
{
PT top = StackTop(&rPath);
printf("(%d,%d)\n", top.row, top.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;
//探测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** 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))
{
PrintPath(&Path);
}
else
{
printf("没有找到通路\n");
}
//销毁迷宫
StackDestroy(&Path);
for (int i = 0; i < N; ++i)
{
free(maze[i]);
}
free(maze);
maze = NULL;
}
return 0;
}
迷宫最短路径求解
小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。
为了让问题简单,假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,
0代表这个位置有障碍物,小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。
小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)
(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),
小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,
向上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值,
当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。
现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。
本题在曾经是美团某一年的笔试题，
本题在上一个题的基础上计入了体力值的概念，
但是本题还有一个隐藏条件，就是要找出迷宫的最短路径，
如下的两个测试用例，需要找出最短路径，才能通过全部测试用例
4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1
10 10 50 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 00 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 11 1 1
链接：https://www.nowcoder.com/questionTerminal/571cfbe764824f03b5c0bfd2eb0a8ddf?f=discussion
题解
同样的，c语言要自己写一个栈，和上面是一样的
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
typedef struct Postion
{
int row;
int col;
}PT;
typedef PT STDataType;
// 支持动态增长的栈
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack, ST;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
//满了 -> 扩容
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity *= 2;
}
}
ps->a[ps->top] = data;
ps->top++;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
///
由于加入了体力值这一变量，路径也就变为不止一条，所以我们还需要初始化一个装最短路径的栈，由图，紫色路径不能满足体力要求，故需要寻找最优路径；
Stack Path;
Stack minPath;
//打印迷宫
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(Stack* ps)
{
//Path数据倒到rPath
Stack rPath;
StackInit(&rPath);
while (!StackEmpty(ps))
{
StackPush(&rPath, StackTop(ps));
StackPop(ps);
}
while (StackSize(&rPath)>1)
{
PT top = StackTop(&rPath);
printf("[%d,%d],", top.row, top.col);
StackPop(&rPath);
}
PT top = StackTop(&rPath);
printf("[%d,%d]", top.row, top.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] == 1)
{
return true;
}
else
{
return false;
}
}
//拷贝最短路径
void StackCopy(Stack*ppath,Stack*pcopy)
{
pcopy->a=(STDataType*)malloc(sizeof(STDataType)*ppath->capacity);
memcpy(pcopy->a,ppath->a,sizeof(STDataType)*ppath->top);
pcopy->top=ppath->top;
pcopy->capacity=ppath->capacity;
}
void GetMazePath(int** maze, int N, int M, PT cur,int p)
{
//核心逻辑
StackPush(&Path, cur);
//如果走到出口
if (cur.row == 0 && cur.col == M - 1)
{
//找到了更短的路径，更新minPath
if(p >= 0 && StackEmpty(&minPath)
|| StackSize(&Path) < StackSize(&minPath))
{
//找到更短路径，更新minPath
StackDestroy(&minPath);
StackCopy(&Path,&minPath);
}
}
//探测cur位置得上下左右四个方向
PT next;
maze[cur.row][cur.col] = 2;
//上
next = cur;
next.row -= 1;
if (IsPass(maze, N, M, next))
{
GetMazePath(maze, N, M, next,p-3);
}
//下
next = cur;
next.row += 1;
if (IsPass(maze, N, M, next))
{
GetMazePath(maze, N, M, next,p);
}
//左
next = cur;
next.col -= 1;
if (IsPass(maze, N, M, next))
{
GetMazePath(maze, N, M, next,p-1);
}
//右
next = cur;
next.col += 1;
if (IsPass(maze, N, M, next))
{
GetMazePath(maze, N, M, next,p-1);
}
// 恢复一下
maze[cur.row][cur.col] = 1;
StackPop(&Path);
}
多条路径之间不能互相干涉，第一条路径走完后，迷宫就被修改了，为了不影响第二条路径，我们需要将迷宫恢复成没走一样的状态
如果不恢复的话，第二条路径无路可走
int main()
{
int N = 0, M = 0,p=0;
while (scanf("%d%d%d", &N, &M, &p) != EOF)
{
//创建迷宫，获取迷宫地图
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);
StackInit(&minPath);
PT entry = { 0,0 };
GetMazePath(maze, N, M, entry,p);
if(!StackEmpty(&minPath))
{
PrintPath(&minPath);
}
else
{
printf("Can not escape!\n");
}
//销毁迷宫
StackDestroy(&Path);
StackDestroy(&minPath);
for (int i = 0; i < N; ++i)
{
free(maze[i]);
}
free(maze);
maze = NULL;
}
return 0;
}
深浅拷贝问题
//找到了更短的路径，更新minPath
if(p >= 0 && StackEmpty(&minPath)
|| StackSize(&Path) < StackSize(&minPath))
{
//找到更短路径，更新minPath
//minPath=Path;
StackDestroy(&minPath);
StackCopy(&Path,&minPath);
}
在c语言中，这里=是直接赋值，就是把它的地址存放数据的地址给你了，如果写minPath=Pah的话，编译器提供的就是浅拷贝，再后面释放内存时，Path已经将那块空间释放了，minPath指向的那块空间已经不是原来的空间了
版权声明：本文为evoke_c原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。