【日常刷题】迷宫问题
描述
定义一个二维数组 N*M ,如 5 × 5 数组下所示:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
输入描述
输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。
输出描述
左上角到右下角的最短路径,格式如样例所示。
分析
这道题我们将要使用动态规划中的回溯的思想,因为我们不能保证走了一步之后,接下来的后几步仍然能走得通,所以我们最好使用递归,然后判断条件是否回溯.
代码
#include <iostream>
#include <vector>
using namespace std;
int ROW;
int COL;
vector<vector<int>> maze;
vector<vector<int>> path_tmp;
vector<vector<int>> path_best;void getbestpath(int i,int j)
{maze[i][j] = 1;path_tmp.push_back({i,j});//如果找到了出口if(i == ROW - 1 && j == COL - 1){//将临时路径和最佳路径进行比较if(path_best.empty() || path_best.size() > path_tmp.size()){//储存最佳路径path_best = path_tmp;}}//如果没有找到出口//向上查找if(i - 1 >= 0 && maze[i-1][j] == 0){getbestpath(i-1,j);}//向下查找if(i + 1 < ROW && maze[i+1][j] == 0){getbestpath(i+1,j);}//向左查找if(j - 1 >= 0 && maze[i][j-1] == 0){getbestpath(i,j-1);}//向右查找if(j + 1 < COL && maze[i][j+1] == 0){getbestpath(i,j+1);}//全部不可走->回溯maze[i][j] = 0;//开放该路径path_tmp.pop_back();
}int main() {while(cin >> ROW >> COL){maze = vector<vector<int>>(ROW,vector<int>(COL,0));// 定义迷宫for(int i = 0; i < ROW; i++)//输入迷宫{for(int j = 0; j < COL ; j++){cin >> maze[i][j];}}getbestpath(0,0);//从(0,0)开始走//打印结果for(int i = 0; i < path_best.size(); i++){cout << "(" << path_best[i][0] << "," << path_best[i][1] << ")" << endl;}}
}相关文章:
【日常刷题】迷宫问题
描述 定义一个二维数组 N*M ,如 5 5 数组下所示: int maze[5][5] { 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走…...
【Python童年游戏】满满的回忆杀—那些年玩过的童年游戏你还记得吗?那个才是你的菜?看到第一个我就泪奔了(致我们逝去的青春)
导语 滴一一学生卡🙌 结伴上车的学生仔子们 用笑声打破车厢的沉默 大人眼里的晚高峰 是给放学后快乐😀时光的加时 下车的学生匆匆起身带起 一阵熟悉的栀子香于💓 是关于校园的记忆 开始零零散散地闪现 放学后集合的秘密基地/跟着城…...
C++ | 认识标准库string和vector
本文概要 本篇文章主要介绍C的标准库类型string和vector,文中描述和代码示例很详细,看完即可掌握,感兴趣的小伙伴快来一起学习吧。 🌟🌟🌟个人简介 🌟🌟🌟 ☀️大家好&a…...
JAVA面试宝典: SpringCloud知识点(通俗易懂易背)
1、什么是 Spring Cloud? Spring Cloud 是基于 Spring Boot 的微服务架构开发工具箱,提供了在分布式系统中构建可靠的、弹性的、灵活的应用所需的大多数工具。Spring Cloud 中包含的子项目如下: Spring Cloud Config:配置管理工具…...
es学习笔记
集群环境下数据往哪个节点放? 路由计算:hash(id) %主分片的数量 集群环境下查数据怎么查? 分配控制:访问任何一个节点都能获取数据,随机访问到的这个节点称为协调节点(访问了当前节点,不一定从当前节点…...
SAS学习第9章:卡方检验之适合性检验与独立性检验
卡方检验就是统计样本的实际观测值与理论推断值之间的偏离程度,实际观测值与理论推断值之间的偏离程度就决定卡方值的大小,如果卡方值越大,二者偏差程度越大;反之,二者偏差越小;若两个值完全相等时…...
马斯克爆料Twitter裁了八成员工;OpenAI CEO:GPT-5根本不存在;小鹏被曝年终奖打0.5折 | AI一周资讯
来源: AI前线 微信号:ai-front 整理 | 凌敏 微软宣布开源 Deep Speed Chat;消息称软银旗下 Arm 启动赴美 IPO;国家网信办出台生成式 AI 管理办法;前理想 AI 芯片一号位骄旸加入三星,负责组建 GPU 团队…… 资 讯 Op…...
ASEMI代理ADG1408YRUZ-REEL7原装ADI车规级ADG1408YRUZ-REEL7
编辑:ll ASEMI代理ADG1408YRUZ-REEL7原装ADI车规级ADG1408YRUZ-REEL7 型号:ADG1408YRUZ-REEL7 品牌:ADI /亚德诺 封装:TSSOP-16 批号:2023 安装类型:表面贴装型 引脚数量:16 类型&#…...
phpstudy本地环境搭建图文教程
作者:Eason_LYC 悲观者预言失败,十言九中。 乐观者创造奇迹,一次即可。 一个人的价值,在于他所拥有的。可以不学无术,但不能一无所有! 技术领域:WEB安全、网络攻防 关注WEB安全、网络攻防。我的…...
【UE 控件蓝图】菜单及功能实现
素材资源连接:百度网盘 请输入提取码 密码:fvcw 效果 步骤 1. 创建蓝图,父类为“HUD” 命名为“MainMenuHUD”并打开 在事件图表中添加如下节点: 2. 创建控件蓝图,命名为“MainMenuWidget” 此时在“MainMenuHUD”的…...
Java 并发编程面试题——Future
目录 1.什么是 Future 模式?Java 中是如何实现的?2.Callable、Future 与 FutureTask 分别是什么?2.1.Callable 接口2.2.Future 接口2.3.FutureTask 类 3.CompletableFuture 类有什么用? 1.什么是 Future 模式?Java 中是…...
SpringBoot 介绍
1.简介 SpringBoot最开始基于Spring4.0设计,是由Pivotal公司提供的框架。 SpringBoot发展史: 2003年Rod Johnson成立Interface公司,产品是SpringFramework2004年,Spring框架开源,公司改名为Spring Source2008年&…...
自动驾驶作业手册
1 总 则 目的为保障港口内自动驾驶车辆安全使用,预防和减少事故,保护人民生命和财产安全,促进港口内业务开展。 含义和范围港口内自动驾驶车辆,是指电脑驾驶车辆,为一种运输动力的无人地面载具,与有人驾驶车辆不同,其具备不需要人类操作即可以感测其环境及导航功能,能…...
MySQL调优笔记——慢SQL优化记录(2)
今天调优的原因是,有一个统计报表业务,查询的时间太慢;同时由于数据库的压力是随机性的,这个业务的执行下限和上限相差近20倍;快的时候可以达到600ms,慢的时候有9秒之多; 接下来详细介绍&#x…...
二叉排序树的插入和删除操作(python实现)
二叉排序树的插入和删除操作都是在保持二叉排序树特性的前提下进行的。 插入操作: 在二叉排序树中插入一个新节点时,先比较新节点的值和当前节点的值的大小关系,若小于当前节点,则继续在当前节点的左子树中查找;若大…...
算法记录 | Day35 贪心算法
860.柠檬水找零 思路: 只需要维护三种金额的数量,5,10和20。 有如下三种情况: 情况一:账单是5,直接收下。情况二:账单是10,消耗一个5,增加一个10情况三:账…...
coinex // 撮合引擎 逻辑流程 (两种数据源 初始化源和前端源)
目录 1 生产者 数据源 1.1. match-server 一启动 初始化数据 自动查询数据库 查询level2要展示的数据 1.2 match-server接收 前端发给Exchange-server的数据 2. 将查询/接受的数据EntrustOrder 转成 Order 解耦 过滤掉不要的属性 3.Order转成 OrderEvent 4. 分配序号发布…...
CentOS7---部署LNMP数据存储到redis
一、部署LNMP及redis 1、部署LNMP,需要将 tengine-2.2.0.tar.gz 拷贝到虚拟机的 /root 目录下 步骤一:安装nginx 源码安装相关软件包 # pcre-devel做正则匹配,zlib-devel做数据压缩 [roottemplate ~]# yum -y install gcc pcre-devel zlib-de…...
Linux中的git命令行
Linux中的git命令行 目录 Linux中的git命令行引入1、Linux下的git工具起源2、gitee的使用.gitignore.git 3、git三板斧3.1 git add3.2 git commit3.3 git push 4、git操作4.1 查看提交日志4.2 查看状态4.3 远端同步4.4 删除文件4.5 修改文件名 引入 当多个开发者同时参与同一个…...
【C++】哈希表:开散列和闭散列
📝 个人主页 :超人不会飞)📑 本文收录专栏:《C的修行之路》💭 如果本文对您有帮助,不妨点赞、收藏、关注支持博主,我们一起进步,共同成长! 目录 前言一、基于哈希表的两个…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
