【日常刷题】迷宫问题
描述
定义一个二维数组 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的修行之路》💭 如果本文对您有帮助,不妨点赞、收藏、关注支持博主,我们一起进步,共同成长! 目录 前言一、基于哈希表的两个…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
