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

简介: 迷宫问题(C语言实现)(牛客网百度笔试真题)

迷宫问题是一种基础的算法问题,需要通过编程实现在一个迷宫中找到从起点到终点的路线。通常使用深度优先搜索或广度优先搜索算法来解决这个问题(主要是使用递归回溯和栈)

具体步骤如下:

1.定义一个二维数组表示迷宫,其中 0 表示可以通过的路,1 表示障碍物。

2.定义起点和终点坐标。

3.使用深度优先搜索或广度优先搜索算法在迷宫中搜索路径,记录经过的路径。

4.如果搜索到终点,则返回路径,否则返回无解。

代码及注释如下

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

运行结果:

迷宫问题的意义

迷宫问题是一类经典的寻路问题,通常被用来测试和研究搜索算法、路径规划算法和人工智能等方面的技术。在现实生活中,迷宫问题的应用场景非常广泛,例如在物流配送中的路径规划、机器人导航、游戏设计和智力竞赛等方面都有应用。此外,解决迷宫问题可以锻炼人的逻辑思维、学习算法的实现和优化、提高计算机编程能力等。

相关文章
|
7月前
|
存储 C语言 C++
C语言------------指针笔试题目深度剖析
C语言------------指针笔试题目深度剖析
47 1
|
4月前
|
存储 小程序 C语言
C语言数据的存储(内含百度笔试题)
C语言数据的存储(内含百度笔试题)
44 4
|
7月前
|
编译器 C语言 C++
从C语言到C++⑥(第二章_类和对象_中篇_续)大练习(日期类)+笔试选择题(下)
从C语言到C++⑥(第二章_类和对象_中篇_续)大练习(日期类)+笔试选择题
54 2
从C语言到C++⑥(第二章_类和对象_中篇_续)大练习(日期类)+笔试选择题(下)
|
7月前
|
存储 算法 C语言
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
65 5
|
7月前
|
算法 编译器 C语言
从C语言到C++⑥(第二章_类和对象_中篇_续)大练习(日期类)+笔试选择题(上)
从C语言到C++⑥(第二章_类和对象_中篇_续)大练习(日期类)+笔试选择题
47 3
|
7月前
|
编译器 C语言 C++
从C语言到C++⑥(第二章_类和对象_中篇_续)大练习(日期类)+笔试选择题(中)
从C语言到C++⑥(第二章_类和对象_中篇_续)大练习(日期类)+笔试选择题
43 1
|
7月前
|
存储 编译器 C语言
从C语言到C++_22(继承)多继承与菱形继承+笔试选择题(下)
从C语言到C++_22(继承)多继承与菱形继承+笔试选择题
52 0
|
7月前
|
Java 编译器 定位技术
从C语言到C++_22(继承)多继承与菱形继承+笔试选择题(中)
从C语言到C++_22(继承)多继承与菱形继承+笔试选择题
49 0
|
7月前
|
安全 程序员 C语言
从C语言到C++_22(继承)多继承与菱形继承+笔试选择题(上)
从C语言到C++_22(继承)多继承与菱形继承+笔试选择题
53 0
|
7月前
|
C语言 C++
从C语言到C++⑧(第二章_类和对象_下篇_续)笔试选择题和OJ题
从C语言到C++⑧(第二章_类和对象_下篇_续)笔试选择题和OJ题
40 0