题解 | #地下迷宫#

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#include<errno.h>
#include<string.h>


typedef struct Postion {//记录位置坐标
    int row;
    int col;
} PT;

//栈的实现
//////////////////////////////////////////////////
typedef PT STDataType;//栈
typedef struct Stack {
    STDataType* a;
    int top;
    int capacity;
} ST;


void StackInit(ST* ps) { //初始化
    assert(ps);

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

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

void StackDestroy(ST* ps) { //销毁
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x) { //在栈顶放入数据

    assert(ps);

    if (ps->top == ps->capacity) {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));

        ps->a = tmp;
        ps->capacity = newcapacity;
    }

    ps->a[ps->top] = x;
    ps->top++;
}
void StackPop(ST* ps) { //删除栈顶数据
    assert(ps);
    assert(ps->top > 0);
    --ps->top;
}
STDataType StackTop(ST* ps) { //取栈顶的数据
    assert(ps);
    assert(ps->top > 0);
    return ps->a[ps->top - 1];
}
int StackSize(ST* ps) { //计算栈内数据个数
    assert(ps);
    return ps->top;
}
bool StackEmpty(ST* ps) { //判断栈是否为空
    assert(ps);
    return ps->top == 0;
}
///////////////////////////////////////////

ST path;
ST minpath;//存储最短路径

bool IsPass(int** maze, int N, int M, PT pos) {//判断当前位置是否越界

    if (pos.row < N && pos.row >= 0 &&
            pos.col >= 0 && pos.col < M &&
            maze[pos.row][pos.col] == 1)
        return true;
    else
        return false;
}

void StackCopy(ST*ppath,ST*pminpath)//把更短的路径给minpath
{
    pminpath->a=(STDataType*)malloc(sizeof(STDataType*) * ppath->capacity);
    memcpy(pminpath->a,ppath->a,sizeof(STDataType)*ppath->top);
    pminpath->top=ppath->top;
    pminpath->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 )//到达终点
    {
        if(P>=0 && StackEmpty(&minpath) ||
        StackSize(&path) < StackSize(&minpath))//判断是否为最小路径
        {
            StackDestroy(&minpath);
            StackCopy(&path,&minpath);
        }
    }
    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);//如果四个方向都不可行，则把栈顶数据去除，再原路径返回

}

void PrintPath(ST* p) {//打印路径
    ST tmp;
    StackInit(&tmp);
    while (!StackEmpty(&minpath)) {
        StackPush(&tmp, StackTop(&minpath));
        StackPop(&minpath);
    }

    while (StackSize(&tmp)>1) {
        printf("[%d,%d],", StackTop(&tmp).row, StackTop(&tmp).col);
        StackPop(&tmp);
    }
    printf("[%d,%d]",StackTop(&tmp).row, StackTop(&tmp).col);
    StackPop(&tmp);
    StackDestroy(&tmp);

}

int main() {

    int a = 0, b = 0,t=0;
    while (scanf("%d %d %d", &a, &b, &t) != EOF) {

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

        for (int i = 0; i < a; i++) {
            maze[i] = (int*)malloc(sizeof(int) * b);
        }

            //输入迷宫
        for (int i = 0; i < a; ++i) {
            for (int k = 0; k < b; ++k) {
                scanf("%d ", &maze[i][k]); 
            }
        }

        StackInit(&path);
        StackInit(&minpath);
        PT begin = { 0, 0 }; //初始位置

        GetMazePath(maze, a, b, begin,t);//找最短路径

        if(!StackEmpty(&minpath))//判断是否找到了
            PrintPath(&minpath);
        else
            printf("Can not escape!\n");
            
        //free空间
        StackDestroy(&path);
        StackDestroy(&minpath);

        for (int i = 0; i < a; ++i) { 
            free(maze[i]);
        }
        free(maze);
        maze = NULL;
    }
    return 0;
}