数据结构-迷宫问题

这篇具有很好参考价值的文章主要介绍了数据结构-迷宫问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


1、题目描述

题目链接:迷宫问题
数据结构-迷宫问题,数据结构,数据结构,c语言,算法,笔记
数据结构-迷宫问题,数据结构,数据结构,c语言,算法,笔记
注意不能斜着走!

2、题目分析

(1)0为可以走,1不能走且只有唯一一条通路
(2)我们可以通过判断上下左右来确定路是否能通过,再设置如果走过的路就用 2 来标记,这样就不会走回头路了,如果有多条能通过,只选择一条路来走
(3)当我们遇到死胡同时,应该返回到上一个位置,再重新判断其他路是否可以走,没有就继续往回退,直到找到下一条路来,像这样的我们就要用到递归了。
(4)因为坐标是2个数据所以我们创建一个结构体来记录坐标。
(5)我们在一进到函数就先保存坐标,再找其他的路,如果没有找到就说明这是一条死胡同,我们就要往后退,再这个过程我们还需要将进来保存的坐标给拿出来,这种后进先出的的数据结构是栈,所以我们要借助栈来实现,不懂栈的可以看看哦:栈
(6)因为栈是先进后出的,所以这跟题目要求不符合,所以我们要再创建一个栈,将另一个栈的数据倒到新的栈里,再输出就符合题目要求了
(7)注意:输出的格式、在结尾还要释放栈和创建的数组、题目可能要求多组测试用例

3、代码实现

#include <stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.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);
void StackDestory(ST* ps);
// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);
STDataType StackTop(ST* ps);

int StackSize(ST* ps);
bool StackEmpty(ST* ps);

void StackInit(ST* ps) {
    assert(ps);

    ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (ps->a == NULL) {
        printf("malloc fail\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, STDataType x) {
    assert(ps);

    // 满了-》增容
    if (ps->top == ps->capacity) {
        STDataType* tmp = (STDataType*)realloc(ps->a,
            ps->capacity * 2 * sizeof(STDataType));
        if (tmp == NULL) {
            printf("realloc fail\n");
            exit(-1);
        }
        else {
            ps->a = tmp;
            ps->capacity *= 2;
        }
    }

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

// 出栈
void StackPop(ST* ps) {
    assert(ps);
    // 栈空了,调用Pop,直接中止程序报错
    assert(ps->top > 0);

    //ps->a[ps->top - 1] = 0;
    ps->top--;
}

STDataType StackTop(ST* ps) {
    assert(ps);
    // 栈空了,调用Top,直接中止程序报错
    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 Pata;//栈
//判断是否有路
bool IsPass(int** maze, int N, int M, PT pos) {
    //(1)判断是否越界
    //(2)判断坐标是否为0
    if (pos.row >= 0 && pos.row < N
        && pos.col >= 0 && pos.col < M
        && maze[pos.row][pos.col] == 0
        ) {
        return true;
    }
    else {
        return false;
    }

}

//打印
void PrintPatar(ST*pata) {
    //再设置一个栈
    ST patar;
    StackInit(&patar);
    //将pata这个栈倒到patar栈里
    while (!StackEmpty(pata)) {
        StackPush(&patar, StackTop(pata));
        StackPop(pata);
    }
    while (!StackEmpty(&patar)) {
        PT top = StackTop(&patar);
        printf("(%d,%d)\n", top.row, top.col);//按照题目的要求打印
        StackPop(&patar);
    }
    //释放
    StackDestory(&patar);
}

bool GetMazePath(int** maze, int N, int M, PT cur) {
    //先入栈
    StackPush(&Pata, cur);
    //改变当前位置
    maze[cur.row][cur.col] = 2;
    //判断是否到出口
    if (cur.row == N - 1 && cur.col == M - 1)
        return true;
    //接下来我们分上下左右判断是否有路可走
    //上
    //记录上的位置
    PT 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(&Pata);
    //走到没路了就返回假
    return false;
}

int main() {
    int N = 0, 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);
        //输入迷宫,0代表可过,1代表不通
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                scanf("%d", &maze[i][j]);
            }
        }
        //初始化,入口
        PT S = { 0, 0 };
        //初始化栈
        StackInit(&Pata);
        //实行
        GetMazePath(maze, N, M, S);
        //打印
        PrintPatar(&Pata);
        //释放栈
        StackDestory(&Pata);
        //释放空间
        for (int i = 0; i < N; i++)
            free(maze[i]);
        free(maze);
        maze = NULL;
    }

    return 0;
}

递归过程:
假设迷宫:

数据结构-迷宫问题,数据结构,数据结构,c语言,算法,笔记
数据结构-迷宫问题,数据结构,数据结构,c语言,算法,笔记
这就是走整个迷宫的流程

以上就是我的分享了,如果有什么错误,欢迎在评论区留言。
最后,谢谢大家的观看!文章来源地址https://www.toymoban.com/news/detail-761174.html

到了这里,关于数据结构-迷宫问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 迷宫求解(包含随机迷宫、求解动画演示)——C语言 数据结构

    该程序是一项 “迷宫求解” 类问题,主要功能包含:         ①25 X 25迷宫的随机生成         ②迷宫求解的动画演示(DFS) 完整代码附最后 : ) 功能演示: 界面展示:  迷宫展示: 结果展示:   首先是随机迷宫部分: 大概思路就是先初始化一个矩阵,外圈为“通

    2024年02月07日
    浏览(63)
  • 数据结构-迷宫问题

    题目链接:迷宫问题 、 注意不能斜着走! (1)0为可以走,1不能走且只有唯一一条通路 (2)我们可以通过判断上下左右来确定路是否能通过,再设置如果走过的路就用 2 来标记,这样就不会走回头路了,如果有多条能通过,只选择一条路来走 (3)当我们遇到死胡同时,应

    2024年02月04日
    浏览(37)
  • 【C数据结构】迷宫问题

    前言: 本章记录作者学习中,遇到的两个比较有趣的问题,一个简单和一个较复杂的迷宫问题。     让我们先来看简单的:迷宫问题 它的具体要求: 输入描述: 输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的 1表示墙壁 , 0表示可以走的路 。

    2024年02月02日
    浏览(38)
  • 【数据结构】迷宫问题实现(包含界面)

    🎈🎈 问题描述:假设迷宫由m行n列构成,有一个入口和一个出口,入口坐标为(1,1),出口坐标为(m,n),试设计并验证一下算法:找出一条入口通往出口的路径,或报告一个\\\"无法通过\\\"的信息。 具体需求如下: 用C语言实现顺序存储结构上队列的基本操作,然后利用该队列的基本操

    2024年02月04日
    浏览(36)
  • 数据结构——迷宫问题(顺序栈、C++)

     讲解: 一、采用二维数组和srand函数随机生成只有0和1的迷宫。 二、求解迷宫大概思路:先将入口处的坐标即方向d入栈,然后当栈不为空时,取出栈顶(即当前节点)的数据。遍历当前节点的四个方向,找到可行的下一个节点,并将其入栈;如没有可行的下一个节点,则将

    2024年02月13日
    浏览(33)
  • 【学习笔记】数据结构算法文档(类C语言)

    1.1.1 线性表的顺序存储表示 1.1.2 顺序表中基本操作的实现 1.1.2.1 初始化 1.1.2.2 取值 1.1.2.3 查找 1.1.2.4 插入 1.1.2.5 删除 1.1.2.6 计数 1.2.1 单链表的定义和表示 ★ 关于结点 1.2.2 单链表基本操作的实现 1.2.2.1 初始化 1.2.2.2 取值 1.2.2.3 查找 1.2.2.4 插入 1.2.2.5 删除 1.2.2.6 前插法创建单

    2024年02月07日
    浏览(42)
  • 【Python数据结构与算法】--- 递归算法的应用 ---[乌龟走迷宫] |人工智能|探索扫地机器人工作原理

    🌈个人主页: Aileen_0v0 🔥系列专栏:PYTHON数据结构与算法学习系列专栏 💫\\\"没有罗马,那就自己创造罗马~\\\"  目录 导言  解决过程  1.建立数据结构 2.探索迷宫: 算法思路 递归调用的“基本结束条件” 3.乌龟走迷宫的实现代码: 运行过程: 拓展: 📝全文总结:  乌龟探索迷宫这个问

    2024年02月05日
    浏览(48)
  • 《数据结构、算法与应用C++语言描述》-列车车厢重排问题

    完整可编译运行代码见:Github::Data-Structures-Algorithms-and-Applications/_10Train_carriages_rearrangement/ 一列货运列车有 n 节车厢,每节车厢要停靠在不同的车站。假设 n个车站从 1 到n 编号,而且货运列车按照从n到1的顺序经过车站。车厢的编号与它们要停靠的车站编号相同。为了便于从

    2024年04月10日
    浏览(61)
  • C语言数据结构——图的最短路径算法解决实例问题

    一、问题描述 W公司在某个地区有6个产品销售点,现根据业务需要打算在其中某个销售点上建立一个中心仓库,负责向其他销售点提供产品。由于运输线路不同,运输费用也不同。假定每天需要向每个销售点运输一次产品,那么应将中心仓库建在哪个销售点上,才能使运输费

    2024年02月08日
    浏览(45)
  • 数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。

    最短路径的算法有两个, Dijkstra算法 和 Floyd算法 。 Dijkstra算法 解决的是 单源 最短路径问题 。 Floyd算法解决的是 多源 最短路径问题,并且可以处理负权图 。 今天要讲的就是Dijkstra算法。 加: feng--Insist (大写的i),进java交流群讨论互联网+技术。可索要PPT等资料。 其他资料

    2024年02月11日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包