数据结构-迷宫问题

文章目录

    • 1、题目描述
    • 2、题目分析
    • 3、代码实现


1、题目描述

题目链接:迷宫问题
在这里插入图片描述
在这里插入图片描述
注意不能斜着走!

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)判断坐标是否为0if (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;
}

递归过程:
假设迷宫:

在这里插入图片描述
在这里插入图片描述
这就是走整个迷宫的流程

以上就是我的分享了,如果有什么错误,欢迎在评论区留言。
最后,谢谢大家的观看!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/218538.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

AI智能化办公:ChatGPT使用方法与技巧

文章目录 ChatGPT简介✨ChatGPT的使用方法✨登录与访问发送请求调整参数 ChatGPT技巧分享✨清晰的提问实验不同的温度值多轮对话 图书推荐✨AI智能化办公内容简介获取方式 AI短视频内容简介获取方式 随着人工智能技术的不断发展&#xff0c;AI助手在办公场景中扮演着越来越重要…

基于Python自动化测试框架之接口测试

上一篇阐述了关于web UI相关的内容&#xff0c;这篇谈谈关于接口测试及自动化测试框架。 接口测试是测试系统组件间数据交互的一种方式&#xff0c;通过不同情况下的输入参数和与之对应的输出结果来判断接口是否符合或满足相应的功能性、安全性要求。简单来说&#xff0c;接口…

UE5 - ArchvizExplorer与Map Border Collection结合 - 实现电子围栏效果

插件地址&#xff1a; https://www.unrealengine.com/marketplace/zh-CN/product/archviz-explorer https://www.unrealengine.com/marketplace/zh-CN/product/map-border-collection ArchvizExplorer扩展&#xff1a; https://download.csdn.net/download/qq_17523181/8843305…

Power BI - 5分钟学习增加索引列

每天5分钟&#xff0c;今天介绍Power BI增加索引列。 什么是增加索引列&#xff1f; 增加索引列就是向表中添加一个具有显式位置值的新列&#xff0c;一般从0或者从1开始。 举例&#xff1a; 首先&#xff0c;导入一张【Sales】样例表(Excel数据源导入请参考每天5分钟第一天)…

消除非受检警告

在Java中&#xff0c;有一些情况下编译器会生成非受检警告&#xff08;Unchecked Warnings&#xff09;。这些警告通常与泛型、类型转换或原始类型相关。消除这些警告可以提高代码的可读性和安全性。以下是一些常见的非受检警告以及如何消除它们的例子&#xff1a; 1. 泛型类型…

【K8S 系列】认识k8s、k8s架构

一、什么是k8s? Kubernetes 简称 k8s&#xff0c;是支持云原生部署的一个平台&#xff0c;k8s 本质上就是用来简化微服务的开发和部署的&#xff0c;用于自动化部署、扩展和管理容器化应用的开源容器编排技术。对于传统的docker其实也提供了容器编排的技术docker-compose&…

机器学习---Boosting

1. Boosting算法 Boosting思想源于三个臭皮匠&#xff0c;胜过诸葛亮。找到许多粗略的经验法则比找到一个单一的、高度预 测的规则要容易得多&#xff0c;也更有效。 预测明天是晴是雨&#xff1f;传统观念&#xff1a;依赖于专家系统&#xff08;A perfect Expert) 以“人无…

学习git后,真正在项目中如何使用?

文章目录 前言下载和安装Git克隆远程仓库PyCharm链接本地Git创建分支修改项目工程并提交到本地仓库推送到远程仓库小结 前言 网上学习git的教程&#xff0c;甚至还有很多可视化很好的git教程&#xff0c;入门git也不是什么难事。但我发现&#xff0c;当我真的要从网上克隆一个…

2044回文字符串(C语言)

目录 一&#xff1a;题目 二&#xff1a;思路分析 1.什么是回文&#xff1f; 2.判断回文&#xff1a; 三&#xff1a;代码 一&#xff1a;题目 二&#xff1a;思路分析 1.什么是回文&#xff1f; 最简单的理解方式就是一个字符串正着写和倒着写一样 2.判断回文&#xff1…

leetcode砍竹子1

现需要将一根长为正整数 bamboo_len 的竹子砍为若干段&#xff0c;每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。 1.根据公式看出取等是在所有n相等的情况&#xff0c;可以得出只有均分 乘积最大 2.转为求下面的最大值 3.求导&#xff0c;得出驻点为e2.7左右 …

百度地图中显示红点

initMap(longitude, latitude) {var map new BMapGL.Map("container");// 创建地图实例if (longitude null || latitude null) {var point new BMapGL.Point(111.1480354849708, 37.5262978563336);var marker new BMapGL.Marker(point);map.addOverlay(marker)…

ubuntu如何远程ssh登录Windows环境并执行测试命令

ubuntu如何远程ssh登录Windows环境并执行测试命令 1 paramiko模块简介1.1 安装paramiko1.2 paramiko基本用法1.2.1 创建SSHClient实例1.2.2 设置主机密钥策略1.2.3 连接SSH服务器1.2.4 执行命令1.2.5 关闭SSH连接1.2.6 异常处理 2 windows的配置2.1 启动OpenSSH服务2.2 配置防火…

【Spark精讲】Spark与MapReduce对比

目录 对比总结 MapReduce流程 ​编辑 MapTask流程 ReduceTask流程 MapReduce原理 阶段划分 Map shuffle Partition Collector Sort Spill Merge Reduce shuffle Copy Merge Sort 对比总结 Map端读取文件&#xff1a;都是需要通过split概念来进行逻辑切片&…

多任务学习(Multi-Task Learning)和迁移学习(Transfer Learning)的详细解释以及区别(系列1)

文章目录 前言一、多任务学习&#xff08;Multi-Task Learning&#xff09;是什么&#xff1f;二、多任务学习&#xff08;Multi-Task Learning&#xff09;对数据的要求三、迁移学习是什么&#xff1f;四&#xff0c;迁移学习对数据的要求五&#xff0c;多任务学习与迁移学习的…

设计模式——外观模式(结构型)

引言 外观模式是一种结构型设计模式&#xff0c; 能为程序库、 框架或其他复杂类提供一个简单的接口。 ​ 问题 假设你必须在代码中使用某个复杂的库或框架中的众多对象。 正常情况下&#xff0c; 你需要负责所有对象的初始化工作、 管理其依赖关系并按正确的顺序执行方法等。…

超详细的80个Python入门实例,附源码,大学装逼必备!

对于大部分Python学习者来说&#xff0c;核心知识基本已经掌握了&#xff0c;但"纸上得来终觉浅,绝知此事要躬行"&#xff0c;要想完全掌握Python&#xff0c;还得靠实践应用。 今天给大家分享80个Python入门实例&#xff0c;都是基础实例&#xff0c;经典实用&…

在datagridview列显示下拉操作

DataGridViewComboBoxExColumn 设定好类型 需要设置的地方是&#xff1a; 绑定数据的操作&#xff1a; 因为此处绑定数据实际为数据 参数 显示的操作&#xff0c;不影响datasource的数据绑定 下一步 数据绑定&#xff1a; DGVCOrderZhuangtai.ValueType typeof(EOrderZhuan…

数据结构 | 查漏补缺之顺式存储和链式存储、如何评价哈希函数的好坏、链地址法、树的遍历、关键路径、完全图、连通图、迪杰斯特拉、b树

目录 顺式存储和链式存储 优缺点比较 顺序存储 ​编辑 链式存储 如何评价哈希函数的好坏 简述哈希查找中链地址法解决冲突的方法 树的遍历 关键路径 完全图 连通图 迪杰斯特拉 b树 特点&#xff1a; 插入&#xff08;索引不能大于&#xff1a;最大为 M-1 个&#…

C程序添加ASAN编译选项

目录 选项说明 环境变量配置 环境变量说明 示例 C程序代码 Cmakelist.txt 测试结果 选项说明 选项说明-fsanitizeaddress开启内存越界检测-fsanitizeleak开启内存泄漏检测-fsanitize-recoveraddress一般后台程序为保证稳定性&#xff0c;不能遇到错误就简单退出&#x…