蓝桥杯算法双周赛心得——迷宫逃脱(记忆化搜索)
大家好,我是晴天学长,非常经典实用的记忆化搜索题,当然也可以用dp做,我也会发dp的题解,需要的小伙伴可以关注支持一下哦!后续会继续更新的。💪💪💪
1) .迷宫逃脱

迷官逃脱[算法赛]
问题描述
在数学王国中,存在- -个大小为N x M的神秘迷言。第i行第j个位置坐标为(i,j),每个位置(i;,j) (1≤i≤N,1≤j≤M)都对应着一个正整数Aij。迷宫的左上角坐标为(1,1), 右下角坐标为(N,M)。
小蓝初始位于坐标(1,1),并携带著Q把密匙。他的目标是移动到迷言的终点,即坐标(N, M)处。但是通往迷宫尽头的道路并不是一-帆风顺的, 在前进的过程中,他遇到了一些奇特的规则。
规则如下:
1.小蓝每次只能向右移动一个位置或向下移动一个位置。
2.当小蓝所在位置的数和下一步移动位置的数互质时,会有一扇封闭的铁门, 小蓝需要消耗-把密匙来打开铁门,打开铁门后,这把钥匙将被摧毁。如果没有密匙,小蓝将无法移动到该位置。
你需要输出小蓝从起点到终点路径之和的最大值,如果无法从起点到达终点,输出-1。
输入格式
第一行输入包含3个整数N, M, Q,分别为迷言的大小和密匙的数量。
接下来输入N行,每行M个整数,为迷言上的数值。
输出格式
输出仅一-行,包含-个整数,表示管案。
样例输入
331
139
样例输出
28
2) .算法思路
逃脱迷宫(记忆化搜索)
1.使用快读接受数据,矩阵大小从11开始,以及使用快输。
2.从重点开始
1.出边界或者要是为-1,就返回最小值
2.到达终点,返回矩阵。
3.记忆化中有就直接返回。
4.当前位置
可以走上面,也可以走下面,取最大值。
存在记忆化的矩阵中。
5.返回结果。
3).算法步骤
1.从第一行读取输入值 N、M 和 Q。
2.创建一个名为 “grid” 的二维数组,维度为 [1100][1100]。
3.读取 N 行输入,并使用这些值填充 grid 数组。
4.将变量 “ans” 初始化为 0。
5.使用参数 N、M、Q 和 grid 调用 dfs() 方法来计算最大和。
6.如果 “ans” 大于 0,则打印其值;否则,打印 -1。
7.刷新输出流。
dfs() 方法执行实际的动态规划计算。它以当前位置 (i, j)、剩余步数 (Q) 和网格作为输入。它使用记忆化技术来存储先前计算过的值,以避免重复计算。
dfs() 方法的步骤如下:
1)检查基本情况:如果 i 或 j 等于 0,或者 Q 等于 -1,则返回 Long.MIN_VALUE。
2)检查当前位置是否为目标位置(即 i = 1 且 j = 1)。如果是,则返回该位置的 grid 值。
3)检查当前位置和剩余步数的结果是否已经被记忆化。如果是,则返回记忆化的结果。
4)根据当前值和左侧值是否互质(最大公约数为 1)来计算 “floor” 值。
5)根据当前值和上方值是否互质来计算 “left” 值。
6)计算结果为当前值与两个递归调用的最大值之和:向左移动(j 减 1)和向上移动(i 减 1)。
7)将结果进行记忆化。
8)返回结果。
gcd() 方法是一个辅助函数,使用欧几里德算法计算两个数的最大公约数。
4). 代码实例
import java.io.*;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static String[] lines;static long[][][] memo = new long[1100][1100][4];static long ans = 0;public static void main(String[] args) throws IOException {lines = in.readLine().split(" ");int N = Integer.parseInt(lines[0]);int M = Integer.parseInt(lines[1]);int Q = Integer.parseInt(lines[2]);long[][] grid = new long[1100][1100];//接受数据for (int i = 1; i <= N; i++) {lines = in.readLine().split(" ");for (int j = 1; j <= M; j++) {grid[i][j] = Integer.parseInt(lines[j - 1]);}}// 开始ans = dfs(N, M, Q, grid);out.println(ans <= 0 ? -1 : ans);out.flush();}private static long dfs(int i, int j, int Q, long[][] grid) {if (i == 0 || j == 0 || Q == -1) return Long.MIN_VALUE;if (i == 1 && j == 1) return grid[i][j];//缓存的值if (memo[i][j][Q]!=0) return memo[i][j][Q];//从上面走,先判断是否互质int floor = gcd((int) grid[i][j], (int) grid[i][j - 1]) == 1 ? 1 : 0;//从左面走int left = gcd((int) grid[i][j], (int) grid[i - 1][j]) == 1 ? 1 : 0;//取最大long result = grid[i][j] + Math.max(dfs(i, j - 1, Q - floor, grid), dfs(i - 1, j, Q - left, grid));memo[i][j][Q] = result;return result;}//求是否互质private static int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
}
4).总结
- 以后建议都用快读快输,不用只过60%,而且这两个还要一起用,只用快读只过95%!!
试题链接:
相关文章:
蓝桥杯算法双周赛心得——迷宫逃脱(记忆化搜索)
大家好,我是晴天学长,非常经典实用的记忆化搜索题,当然也可以用dp做,我也会发dp的题解,需要的小伙伴可以关注支持一下哦!后续会继续更新的。💪💪💪 1) .迷宫逃脱 迷官逃脱…...
nodejs+vue线上生活超市购物商城系统w2c42
超市管理系统的开发流程包括对超市管理系统的需求分析,软件的设计建模以及编写程序实现系统所需功能这三个阶段。对超市管理系统的需求分析。在这个阶段,通过查阅书籍,走访商场搜集相关资料,了解经营者对软件功能的具体所需和建议…...
飞翔的小鸟
运行游戏如下: 碰到柱子就结束游戏 App GameApp类 package App;import main.GameFrame;public class GameApp {public static void main(String[] args) {//游戏的入口new GameFrame();} } main Barrier 类 package main;import util.Constant; import util.Ga…...
浅析OKR的敏捷性
前言 OKR对于工作的提升有着一定的不可替代的作用。特别在敏捷方面。 OKR的敏捷性 OKR(Objectives and Key Results)是一种目标设定框架,它的敏捷性主要体现在以下几个方面: 公开透明 OKR要求完全公开透明,让每个员…...
Linux+qt:创建动态库so,以及如何使用(详细步骤)
目录 1、根据安装Qt Creator的向导进行创建 2、开发动态库注意的一些细节 3、给动态库添加一个对外开放的接口文件 4、了解下Qt的 .pri文件(非常实用) 5、如何调用动态库.so 1、根据安装Qt Creator的向导进行创建 (1)选择“…...
如何将Docker的构建时间减少40%
与许多公司类似,我们为产品中使用的所有组件构建docker映像。随着时间的推移,其中一些映像变得越来越大,我们的CI构建花费的时间也越来越长。我的目标是CI构建不超过5分钟——差不多是喝杯咖啡休息的理想时间。如果构建花费的时间超过这个时间…...
二分查找——经典题目合集
文章目录 🦜69. x 的平方根🌼题目🌻算法原理🌷代码实现 🐳35. 搜索插入位置🌼题目🌻算法原理🌷代码实现 🦭852. 山脉数组的峰顶索引🌼题目🌻算法原…...
在Jupyter Lab中使用多个环境,及魔法命令简介
一、Jupyter Lab使用conda虚拟环境 1、给虚拟环境添加 ipykernel 方法一: 创建环境时直接添加ipykernel 方法:conda create -n 【虚拟环境名称】python3.8 ipykernel实例如下: conda create -n tensorflow_cpu python3.8 ipykernel 方法二ÿ…...
知虾数据软件:电商人必备知虾数据软件,轻松掌握市场趋势
在当今数字化时代,数据已经成为了企业决策的重要依据。对于电商行业来说,数据更是至关重要。如果你想在电商领域中脱颖而出,那么你需要一款强大的数据分析工具来帮助你更好地了解市场、分析竞争对手、优化运营策略。而知虾数据软件就是这样一…...
c语言中*p1++和p1++有啥区别
在C语言中,*p1和p1是两个不同的表达式,有以下区别: *p1:这是一个后缀递增运算符的组合。首先,*p1会取出指针p1所指向的值,并且对p1进行递增操作。简而言之,这个表达式会先取出p1指向的值&#x…...
2
【任务 2】私有云服务运维[10 分] 【适用平台】私有云 【题目 1】OpenStack 开放镜像权限[0.5 分] 使 用 OpenStack 私 有 云 平 台 , 在 OpenStack 平台的 admin 项 目 中 使 用 cirros-0.3.4-x86_64-disk.img 镜像文件创建名为 glance-cirros 的镜像,通…...
SELinux零知识学习二十二、SELinux策略语言之类型强制(7)
接前一篇文章:SELinux零知识学习二十一、SELinux策略语言之类型强制(6) 二、SELinux策略语言之类型强制 3. 访问向量规则 AV规则就是按照对客体类别的访问许可指定具体含义的规则,SELinux策略语言目前支持四类AV规则:…...
cadence layout lvs时出现error
Error:Schematic export failed or was cancelled.Please consult the transcript in the viewer window. 解决办法同下: cadence layout lvs时出现error-CSDN博客...
python练习题(markdown中的60道题)
1.Demo01 摄氏温度转化为华氏温度 celsius float(input(输入摄氏温度:)) fahrenheit (9/5)*celsius 32 print(%0.1f 摄氏温度转为华氏温度为 %0.1f % (celsius, fahrenheit))结果: 2.Demo02 计算圆柱体的体积 h, r map(float, input().split())# …...
【JavaSE】-4-单层循环结构
回顾 运算符: 算术 --、逻辑 && & || |、比较 、三元 、赋值 int i 1; i; j i; //j2 i3 syso(--j"-----"i) //1 3 选择结构 if(){} if(){}else{} if(){}else if(){}else if(){}else{}//支持byte、short、int //支持char //支持枚举…...
12、人工智能、机器学习、深度学习的关系
很多年前听一个机器学习的公开课,在Q&A环节,一个同学问了老师一个问题“机器学习和深度学习是什么关系”? 老师先没回答,而是反问了在场的同学,结果问了2-3个,没有人可以回答的很到位,我当时也是初学一脸懵,会场准备的小礼品也没有拿到。 后来老师解释“机器学习和…...
webpack external 详解
作用:打包时将依赖独立出来,在运行时(runtime)再从外部获取这些扩展依赖,目的时解决打包文件过大的问题。 使用方法: 附上代码块 config.set(externals, {vue: Vue,vue-router: VueRouter,axios: axios,an…...
代码混淆不再愁:一篇掌握核心技巧
1. 概述 代码混淆是将计算机程序的代码转换成一种功能上等价,但是难以阅读和理解的形式。 对于软件开发者来说,代码混淆可以在一定程度上保护程序免被逆向。 对于逆向工程师来说,学习代码混淆可以帮助我们研究反混淆技术。 2. 常见混淆…...
华为云IoT与OpenHarmony深度协同,加速设备上鸿即上云【云驻共创】
本次专题论坛探讨了华为云IoT与Open Harmony的深度协同、边缘屏蔽硬件差异、实现智慧隧道全方位智能化管理,以及华为云与Open Harmony生态的合作。同时也介绍了华为云物联网卡平台、HTTP2协议以及华为物联网在交通领域的应用。 一.华为云IoT与Open Harm…...
深入浅出 Linux 中的 ARM IOMMU SMMU I
Linux 系统下的 SMMU 介绍 在计算机系统架构中,与传统的用于 CPU 访问内存的管理的 MMU 类似,IOMMU (Input Output Memory Management Unit) 将来自系统 I/O 设备的 DMA 请求传递到系统互连之前,它会先转换请求的地址,并对系统 I…...
【AI面试临阵磨枪-42】向量数据库选型:Milvus、Chroma、Pinecone、FAISS 区别
一、面试题目面试官:请对比 Milvus、Chroma、Pinecone、FAISS 四款主流向量数据库,说明它们的架构、优缺点、适用场景、工程选型。二、知识储备1. 一句话定位(面试必背)FAISS:Facebook 开源向量检索库,不是…...
【配置指南】华为交换机的时间配置
在生产网络里,很多人会忽略一个看似不起眼的东西——设备时间。 但真实情况是: 日志对不上 故障追溯困难 安全审计失败 这些问题,80%都和时间配置有关。 本文带你一次搞懂:华为交换机如何正确配置时间(手动 + 自动 + NTP) 一、UTC到底是什么 UTC(Coordinated Unive…...
二向箔压缩测试极限挑战
一、从科幻到现实:二向箔压缩测试的概念溯源刘慈欣科幻巨著《三体》中,二向箔作为宇宙规律武器,能将三维空间及物质不可逆坍缩为二维平面,其核心逻辑是“降维”“压缩”与“信息损耗”。当我们以软件测试从业者的视角审视这一概念…...
嵌入式系统行为建模:原子化需求与UML状态机实践
1. 嵌入式系统行为建模的核心挑战在嵌入式系统开发领域,我们经常面临一个根本性矛盾:系统功能日益复杂,但市场窗口期却越来越短。以智能家居网关开发为例,十年前可能只需要处理简单的协议转换,而现在要同时支持语音交互…...
Node.js服务端应用接入Taotoken调用大模型的完整代码示例
Node.js 服务端应用接入 Taotoken 调用大模型的完整代码示例 1. 环境准备与依赖安装 在开始编写 Node.js 服务端代码前,需要确保开发环境已安装 Node.js(建议版本 16 或更高)和 npm。创建一个新的项目目录并初始化: mkdir taot…...
tabula-java扩展开发指南:如何实现自定义表格提取算法
tabula-java扩展开发指南:如何实现自定义表格提取算法 【免费下载链接】tabula-java Extract tables from PDF files 项目地址: https://gitcode.com/gh_mirrors/ta/tabula-java 在处理PDF文件时,从复杂格式中准确提取表格数据一直是开发者面临的…...
AI智能体开发新范式:引入节奏与记忆系统优化长期任务执行
1. 项目概述:当AI智能体学会“呼吸”与“节奏”在AI智能体开发领域,我们常常陷入一个误区:追求极致的单次响应速度与逻辑推理的深度,却忽略了智能体作为一个持续运行的“生命体”所应有的“节奏感”。想象一下,一个不知…...
零基础吃透 Java 面向对象:类、对象、this 与 static 实战
Java 面向对象基础:类与对象一、章节整体框架本章共六大核心模块,由浅入深构建面向对象知识体系:1. 面向对象概述2. 类的定义3. 对象的创建与使用4. 方法重载5. this 关键字6. static 关键字本章内容是后续封装、继承、多态的基础。二、面向对…...
JetBrains Godot开发工具套件:提升GDScript与C#游戏开发效率
1. 项目概述:JetBrains Godot 开发工具套件如果你是一名使用 Godot 引擎的游戏开发者,并且恰好也是 JetBrains 全家桶的忠实用户,那么你很可能已经对代码编辑体验的“割裂感”深有体会。一边是 Godot 内置编辑器对 GDScript 的原生友好&#…...
飞书日历API实战:基于Node.js与OAuth构建自动化日程助手
1. 项目概述:一个能听懂人话的飞书日历助手 最近在折腾自动化流程,发现一个挺高频的需求:把那些零散的日程安排,从聊天对话里直接同步到日历。比如同事在飞书群里说“下周三下午三点开个会”,或者自己随手记的“周五记…...
