题解 | #迷宫问题#

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#include<errno.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;

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] == 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;

    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;
}

void PrintPath(ST* ps) {//用临时栈返回打印数据
    ST tmp;
    StackInit(&tmp);
    while (!StackEmpty(&path)) {
        StackPush(&tmp, StackTop(&path));
        StackPop(&path);
    }

    while (!StackEmpty(&tmp)) {
        printf("(%d,%d)\n", StackTop(&tmp).row, StackTop(&tmp).col);
        StackPop(&tmp);
    }
    StackDestroy(&tmp);
}

int main() {

    int a = 0, b = 0;
    while (scanf("%d %d", &a, &b) != 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);
        PT begin = { 0, 0 }; //初始位置

        if (GetMazePath(maze, a, b, begin))//判断是否找到路径
            PrintPath(&path);
        else
            printf("没有找到通路\n");

        StackDestroy(&path);

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