迷宫问题求解

在这里插入图片描述
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 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/evoke_c/article/details/118078771