【日常刷题】迷宫问题
描述
定义一个二维数组 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的修行之路》💭 如果本文对您有帮助,不妨点赞、收藏、关注支持博主,我们一起进步,共同成长! 目录 前言一、基于哈希表的两个…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...
