迷宫最短路径问题

2022-11-10 15:06:55 浏览数 (1)

一.迷宫最短路径问题

小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单,假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍物,小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值,当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。

输入描述： 输入包括n 1行: 第一行为三个整数n,m(3 <= m,n <= 10),P(1 <= P <= 100) 接下来的n行: 每行m个0或者1,以空格分隔 输出描述： 如果能逃离迷宫,则输出一行体力消耗最小的路径,输出格式见样例所示;如果不能逃离迷宫,则输出"Can not escape!"。 测试数据保证答案唯一 示例1 输入： 4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 复制 输出： [0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]

原题来自于：来自于牛客网的地下迷宫 这道题跟常规迷宫问题大体相似，只不过引入了体力值的消耗问题 相比较上次的常规迷宫问题，这次的1是通路 ，0是墙壁

1. 整体过程

这里前面的过程就不说了，需要的可以看：迷宫常规问题 主要从找到通路后，回溯后走到另一条路开始

1.此时走到下标(0,3)时找到出口，回溯时发现只有达到下标(2,2)时 ，右方向可以走， 2.因为我们遵循 上下左右 四个方向依次递归，所以是当下标(2,2)完成了下的递归 回溯后，只有左右两个方向可以走

当此次完成后的路径path与minpath最短路径比较，发现此时为最短路径。

1.minpath与path之间不能直接拷贝(浅拷贝问题)

path 作为当前路径，minpath作为最短路径，当path值小于minpath值时，需要把path值赋值给minpath，但是如果我们此时单纯赋值处理的话会出现问题

1.把path赋值给minpath，此时的minpath原来的空间就丢了，造成内存泄漏 2.此时的赋值是将minpath指向path的空间，因为两者都需要内存销毁，就会导致内存销毁两次

所以为了防止这种情况的发生 将minpath原有的空间销毁掉，再动态开辟一块跟path相同大小的空间，并将path的值拷贝过来

代码语言：javascript复制
void stackcopy(ST* minpath, ST* path)
{
        minpath->a = (datatype*)malloc(sizeof(datatype*) * path->capacity);//动态开辟一块与path一样大的空间
        memcpy(minpath->a, path->a, sizeof(datatype) * path->top);//使用内存拷贝函数将path的内容拷贝过来
        minpath->top = path->top;
        minpath->capacity = path->capacity;
}

2.找到一次通路后，如何处置已经变为2的路径

在回溯的过程中，把变成2的通路置成1 回溯的判断:如果上下左右四个方向都不可以走，就回溯。 如图此时寻找到出口后，先将出口下标置成2，再判断此时上下左右都不能走，在回溯到上一层之前，才把出口下标置成1

3. getmazepath不需要判断是否为真

在常规迷宫问题中只要找到通路就可以了，但是在 最短路径中，我们需要考虑到所有情况， 每次找到通路的path 与minpath值比较 ，找到最短路径， 加true 用于只判断一次通路的情况，不加true可以判断所有通路的情况

代码语言：javascript复制
ST path;
ST minpath;
void stackcopy(ST* minpath, ST* path)
{
        minpath->a = (datatype*)malloc(sizeof(datatype*) * path->capacity);
        memcpy(minpath->a, path->a, sizeof(datatype) * path->top);
        minpath->top = path->top;
        minpath->capacity = path->capacity;
}
void  getmazepath(int** maze, int N, int M, PT cur,int p)
{
    stackpush(&amp;path, cur);//入栈
    if (cur.row == 0 &amp;&amp; cur.col == M - 1)//出口
    {
        //找到最短路径，更新minpath 要保证体力>=0
        if (p >= 0 &amp;&amp; stackempty(&amp;minpath) || stacksize(&amp;path) < stacksize(&amp;minpath))
        {
            stackdestroy(&amp;minpath);
            stackcopy(&amp;minpath, &amp;path);//将path赋给minpath
        }
    }
    maze[cur.row][cur.col] = 2;//先将目前所处位置赋值为2 
    PT next;

    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(&amp;path);   //如果上下左右都不满足就移除栈顶元素
}

4.整体代码

代码语言：javascript复制
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.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)//现在为1为通道，0为墙壁
{
    if (pos.row >= 0 &amp;&amp; pos.row < N &amp;&amp; pos.col >= 0 &amp;&amp; pos.col < M &amp;&amp; maze[pos.row][pos.col] == 1)
    {   //坐标不越界并且该处位置==1
        return true;
    }
    else
    {
        return false;
    }
}
ST path;
ST minpath;
void stackcopy(ST* minpath, ST* path)
{
        minpath->a = (datatype*)malloc(sizeof(datatype*) * path->capacity);
        memcpy(minpath->a, path->a, sizeof(datatype) * path->top);
        minpath->top = path->top;
        minpath->capacity = path->capacity;
}
void  getmazepath(int** maze, int N, int M, PT cur,int p)
{
    stackpush(&amp;path, cur);//入栈
    if (cur.row == 0 &amp;&amp; cur.col == M - 1)//出口
    {
        //找到最短路径，更新minpath 要保证体力>=0
        if (p >= 0 &amp;&amp; stackempty(&amp;minpath) || stacksize(&amp;path) < stacksize(&amp;minpath))
        {
            stackdestroy(&amp;minpath);
            stackcopy(&amp;minpath, &amp;path);//将path赋给minpath
        }
    }
    maze[cur.row][cur.col] = 2;//先将目前所处位置赋值为2 
    PT next;

    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(&amp;path);   //如果上下左右都不满足就移除栈顶元素
}
void printpath(ST* ps)//由于此时的path栈要打印出来会倒着出，
//所以又重新创建了一个栈，将数据导进去
{
    ST rpath;
    stackinit(&amp;rpath);
    while (!stackempty(ps))
    {
        stackpush(&amp;rpath, stacktop(ps));
        stackpop(ps);
    }
    while (stacksize(&amp;rpath)>1)
    {
        PT top = stacktop(&amp;rpath);//此时数据类型被改为PT
        printf("[%d,%d],", top.row, top.col);
        stackpop(&amp;rpath);
    }
    PT top = stacktop(&amp;rpath);//此时数据类型被改为PT
    printf("[%d,%d]", top.row, top.col);
    stackpop(&amp;rpath);
    stackdestroy(&amp;rpath);//内存销毁
}
int main()
{
    int N = 0;
    int M = 0;
    int p = 0;
    while (scanf("%d%d%d", &amp;N, &amp;M,&amp;p) != 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", &amp;maze[i][j]);
            }
        }
        PT  entry = { 0,0 };
    
        stackinit(&amp;path);
        stackinit(&amp;minpath);
        getmazepath(maze, N, M, entry, p);
        if (!stackempty(&amp;minpath))//如果最短路径因为体力问题为0 
        {
            printpath(&amp;minpath);
        }
        else
        {
            printf("Can not escape!");
        }

        stackdestroy(&amp;path);
        stackdestroy(&amp;minpath);

        //释放空间
        //1.释放N个数组指针指向的空间
        for (i = 0; i < N; i  )
        {
            free(maze[i]);
        }
        //2.将N个指针数组整体释放
        free(maze);
        maze = NULL;
    }

    return 0;
}
path

0 人点赞