题解 | #地下迷宫#

C语言写的！嘻嘻

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<stdbool.h>

#include<assert.h>

typedef struct position

{

    int col;

    int row;

}PS;

////////////////////////////////////////////////////////////////////////////////

typedef PS  StackDataType;

typedef struct Stack

{

    StackDataType* a;

    int top;

    int capacity;

}Stack;

void StackInit(Stack* ps)

{

    ps->a = (StackDataType*)malloc(sizeof(StackDataType) * 4);

    ps->capacity = 4;

    ps->top = 0;

}

void StackDestroy(Stack* ps)

{

    free(ps->a);

    ps->a = NULL;

    ps->top = ps->capacity = 0;

}

void StackPush(Stack* ps, StackDataType x)

{

    assert(ps);

    if (ps->capacity == ps->top)

    {

        StackDataType* temp = (StackDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(StackDataType));

        if (temp == NULL)

        {

            printf("realloc fails\n");

            exit(-1);

        }

        ps->a = temp;

        ps->capacity *= 2;

    }

    ps->a[ps->top] = x;

    ps->top++;

}

void StackPop(Stack* ps)

{

    assert(ps);

    assert(ps->top > 0);

    ps->top--;

}

int StackSize(Stack* ps)

{

    assert(ps);

    return ps->top;

}

bool StackEmpty(Stack* ps)

{

    assert(ps);

    return ps->top == 0;

}

StackDataType StackTop(Stack* ps)

{

    assert(ps);

    return ps->a[ps->top - 1];

}

/// ////////////////////////////////////////////////////////////////////////////

void printpath(Stack* path, Stack* repath)

{

    while (!StackEmpty(path))

    {

        PS top = StackTop(path);

        StackPush(repath, top);

        StackPop(path);

    }

    while (repath->top>1)

    {

        PS top = StackTop(repath);

        printf("[%d,%d],", top.col, top.row);

        StackPop(repath);

    }

    PS top = StackTop(repath);

    printf("[%d,%d]", top.col, top.row);

}

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");

}

bool isnext(int** maze, int n, int m, PS next,int p)

{

    if (next.col >= 0 && next.col < n && next.row >= 0 && next.row < m &&

        maze[next.col][next.row] == 1&&p>=0)

    {

        maze[next.col][next.row] = 2;

        return true;

    }

    return false;

}

void Getpath(int** maze, int n, int m, PS cur, Stack* path,Stack* minpath,int p)

{

    StackPush(path, cur);

    if (cur.col == 0 && cur.row == m - 1&&p>=0)

    {

        if (StackEmpty(minpath)||StackSize(path)<StackSize(minpath))

        {

            StackDestroy(minpath);

            minpath->a = (StackDataType*)malloc(sizeof(StackDataType) * path->capacity);

            assert(minpath->a);

            memcpy(minpath->a, path->a, sizeof(StackDataType) * path->top);

            minpath->top = path->top;

            minpath->capacity = path->capacity;

        }

        StackPop(path);

        return ;

    }

    //下

    PS next = cur;

    next.col++;

    if (isnext(maze, n, m, next,p))

    {

        Getpath(maze, n, m, next, path,minpath,p);

        maze[next.col][next.row] = 1;

    }

    //上

    next = cur;

    next.col--;

    if (isnext(maze, n, m, next,p-3))

    {

        Getpath(maze, n, m, next, path,minpath,p-3);

        maze[next.col][next.row]=1;

    }

    //右

    next = cur;

    next.row++;

    if (isnext(maze, n, m, next,p-1))

    {

        Getpath(maze, n, m, next, path,minpath,p-1);

        maze[next.col][next.row] = 1;

    }

    //左

    next = cur;

    next.row--;

    if (isnext(maze, n, m, next,p-1))

    {

        Getpath(maze, n, m, next, path,minpath,p-1);

        maze[next.col][next.row] = 1;

    }

    StackPop(path);

    return;

}

int main()

{

    Stack path, repath,minpath;

    StackInit(&path);

    StackInit(&repath);

    StackInit(&minpath);

    PS GPS = { 0,0 };

    int n = 0, m = 0, ** maze = NULL,p=0;

    while (scanf("%d%d%d", &n, &m,&p) != EOF)

    {

        maze = (int**)malloc(sizeof(int*) * n);

        assert(maze);

        for (int i = 0;i < n;i++)

        {

            maze[i] = (int*)malloc(sizeof(int) * m);

            assert(maze[i]);

        }

        for (int i = 0;i < n;i++)

        {

            for (int j = 0;j < m;j++)

            {

                scanf("%d", &maze[i][j]);

            }

        }

        maze[0][0] = 2;

        /*printf("\n");

        printmaze(maze,n,m);*/

        Getpath(maze, n, m, GPS, &path,&minpath,p);

        if (minpath.top > 1)

            printpath(&minpath, &repath);

        else

            printf("Can not escape!");

        for (int i = 0;i < n;i++)

        {

            free(maze[i]);

        }

        free(maze);

        maze = NULL;

        StackDestroy(&path);

        StackDestroy(&repath);

        StackDestroy(&minpath);

    }

    return 0;

}