迷宫问题（C语言实现）（牛客网百度笔试真题）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//迷宫问题
//用结构体存迷宫的坐标
typedef struct Maze
{
    int row;
    int col;
}PT;
//由于C语言没有栈的库，所以用‘-’分隔一下栈相关的代码
//-------------------------------------------------------------------
typedef PT Type;//Tpye表示的是PT结构体类型
typedef struct Stack
{
    Type* a;
    int top;//栈顶
    int capacity;//容积
}ST;
void StackInit(ST* ps);
void StackDestory(ST* ps);
//栈顶插入删除数据
//入栈
void StackPush(ST* ps, Type x);
//出栈
void StackPop(ST* ps);
Type StackTop(ST* ps);
int StackSize(ST* ps);
bool StackEmpty(ST* ps);
//初始化
void StackInit(ST* ps)
{
    assert(ps);
    ps->a = (Type*)malloc(sizeof(Type) * 4);
    if (ps->a == NULL)
    {
        printf("扩容失败\n");
        exit(-1);
    }
    ps->capacity = 4;
    ps->top = 0;
}
//销毁
void StackDestory(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}
//栈顶插入删除数据
//入栈（插入）
void StackPush(ST* ps, Type x)
{
    assert(ps);
    //满了就增容
    if (ps->top == ps->capacity)
    {
        Type* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(Type));
        if (tmp == NULL)
        {
            printf("扩容失败\n");
            exit(-1);
        }
        else
        {
            ps->a = tmp;
            ps->capacity *= 2;
        }
    }
    ps->a[ps->top] = x;
    ps->top++;
}
//出栈（删除）
void StackPop(ST* ps)
{
    assert(ps);
    //栈空了，直接终止
    assert(ps->top > 0);
    ps->top--;
}
//
Type 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;//定义一个全局的栈，用来存放迷宫路径位置的坐标
//----------------------------------------------------------------------------
//输出坐标
//（由于我们把坐标存入栈时的顺序和题目要求的顺序一样，就会导致出栈时坐标是反着出的
//，因此就需要倒置栈中的元素）【具体操作就看下面的PrintPath函数】
void PrintPath()//由于path是全局变量，就不需要再传参了
{
    //将栈里元素入到另外一个栈里面
    //再输出另外一个栈的元素，就实现了倒置
    ST rpath;//用这个栈来输出
    StackInit(&rpath);//初始化栈
    while (!StackEmpty(&path))//把path中的元素入到rpath中来
    {
        StackPush(&rpath, StackTop(&path));
        StackPop(&path);
    }
    while (!StackEmpty(&rpath))//再输出rpath中的元素，就就实现了倒置
    {
        PT top = StackTop(&rpath);
        printf("(%d,%d)\n", top.row, top.col);
        StackPop(&rpath);
    }
    StackDestory(&rpath);
}
//测试迷宫图是否正确（不写这个函数也行）
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");
    }
}
//判断该位置是否能走
int IsPass(int** maze, int n, int m, PT cur)
{
    //坐标不能越界且该位置值为0
    if (cur.col >= 0 && cur.row >= 0
        && cur.col < m && cur.row < n
        && maze[cur.row][cur.col] == 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
//判断迷宫是否能走到出口（递归回溯）
//（如果该位置能走通，就入栈，走不通（死路），就把该位置坐标弹出栈）
int MazePath(int** maze, int n, int m, PT cur)//cur表示从迷宫走的起始位置坐标
{
    StackPush(&path, cur);//入栈
    //如果走到出口
    if (cur.row == n - 1 && cur.col == m - 1)
    {
        return 1;
    }
    //探测上下左右四个方向
    PT next;//定义一个存放下一个位置坐标的结构变量
    maze[cur.row][cur.col] = 2;//把走过的位置设为2，以防死递归
    //上
    next = cur;
    next.row -= 1;
    //如果下一个位置能走，就递归【上下左右同理】
    if (IsPass(maze, n, m, next))
    {
        if (MazePath(maze, n, m, next))
            return 1;
    }
    //下
    next = cur;
    next.row += 1;
    if (IsPass(maze, n, m, next))
    {
        if (MazePath(maze, n, m, next))
            return 1;
    }
    //左
    next = cur;
    next.col -= 1;
    if (IsPass(maze, n, m, next))
    {
        if (MazePath(maze, n, m, next))
            return 1;
    }
    //右
    next = cur;
    next.col += 1;
    if (IsPass(maze, n, m, next))
    {
        if (MazePath(maze, n, m, next))
            return 1;
    }
    //如果上下左右都不通，就把该位置坐标弹出栈
    StackPop(&path);//出栈
    return 0;
}
int main()
{
    int N = 0;
    int 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 str = { 0,0 };
        if (MazePath(maze, N, M, str))
        {
            //找到了
            PrintPath();
        }
        else
        {
            printf("未找到");
        }
        StackDestory(&path);
        for (int i = 0; i < N; i++)
        {
            free(maze[i]);
        }
        free(maze);
        maze = NULL;
    }
    return 0;
}