蓝桥杯算法双周赛心得——迷宫逃脱(记忆化搜索)

大家好,我是晴天学长,非常经典实用的记忆化搜索题,当然也可以用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%!!

试题链接:

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

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

相关文章

Mac | Vmware Fusion | 分辨率自动还原问题解决

1. 问题 Mac的Vmware Fusion在使用Windows10虚拟机时&#xff0c;默认显示器配置如下&#xff1a; 开机进入系统并变更默认分辨率后&#xff0c;只要被 ⌘Tab 切换分辨率就会还原到默认&#xff0c;非常影响体验。 2. 解决方式 调整 设置 -> 显示器 -> 虚拟机分辨率…

Authing CEO 谢扬来信 |我的原则

从忙碌的工作中短暂抽身&#xff0c;有很多感想&#xff0c;不吐不快&#xff0c;借此机会&#xff0c;倾我所有&#xff0c;诉我原则。 原则一&#xff1a;坚强信念&#xff0c;坚定意志 商人大多「无利不起早」&#xff0c;而创业者的反馈周期比商人长非常非常多。 相比「商品…

【Linux进阶之路】进程间通信

文章目录 一、原理二、方式1.管道1.1匿名管道1.1.1通信原理1.1.2接口使用 1.2命名管道 2.共享内存2.1原理2.2接口使用 3.消息队列原理 4.信号量引入原理 总结 一、原理 进程间的通信是什么&#xff1f;解释&#xff1a; 简单理解就是&#xff0c;不同进程之间进行数据的输入输出…

2023 hnust 湖南科技大学 信息安全管理课程 期中考试 复习资料

前言 ※老师没画重点的补充内容★往年试卷中多次出现或老师提过的&#xff0c;很可能考该笔记是奔着及格线去的&#xff0c;不是奔着90由于没有听过课&#xff0c;部分知识点不一定全&#xff0c;答案不一定完全正确最新版请转至Github 题型 试卷有很多题是原题&#xff0c;分…

二十一、数组(6)

本章概要 数组排序Arrays.sort的使用并行排序binarySearch二分查找parallelPrefix并行前缀 数组排序 根据对象的实际类型执行比较排序。一种方法是为不同的类型编写对应的排序方法&#xff0c;但是这样的代码不能复用。 编程设计的一个主要目标是“将易变的元素与稳定的元素…

一文读懂现代化数据中心DCIM系统容量管理的几个维度

数据中心是现代科技领域不可或缺的基础设施&#xff0c;其承载着大量的计算、存储和网络资源&#xff0c;是众多行业业务数字化的起点&#xff0c;更是衡量企业数字化能力的关键因素。数据中心DCIM&#xff08;Data Center Infrastructure management&#xff09;&#xff0c;即…

linaro交叉编译工具链下载与使用笔记

笔记 文章目录 笔记确定目标 &#xff08;aarch64&#xff09;选择版本&#xff08;7.5&#xff09;选择目标&#xff08;aarch64-linux-gnu&#xff09;下载地址工具链&#xff08;gcc-linaro-7.5.0-2019.12-x86_64_aarch64-linux-gnu.tar.xz&#xff09;编译测试 &#xff08…

nginx国密ssl测试

文章目录 文件准备编译部署nginx申请国密数字证书配置证书并测试 文件准备 下载文件并上传到服务器&#xff0c;这里使用centos 7.8 本文涉及的程序文件已打包可以直接下载。 点击下载 下载国密版openssl https://www.gmssl.cn/gmssl/index.jsp 下载稳定版nginx http://n…

hutool工具连接数据库实现数据处理重新入库

1 引入依赖 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.7.18</version></dependency><!--mysql驱动包--><dependency><groupId>mysql</groupId><ar…

【Unity】EventSystem.current.IsPointerOverGameObject()对碰撞体起作用

本来我是用 EventSystem.current.IsPointerOverGameObject()来检测是否点击在UI上的&#xff0c;但是发现&#xff0c;他对我的碰撞体也是返回ture,研究半天。。。。找不出问题&#xff0c;然后发现我的相机上挂载了PhysicsRaycaster&#xff0c;去掉之后就好了&#xff0c;至于…

无代码未来:智能、可视化、自动化的融合

无代码是一个相对较新的概念&#xff0c;不同的人群对其界定可能存在一定的差异。 对于IT专业人士和开发人员而言&#xff0c;无代码通常是指使用可视化界面和拖拽操作来构建应用程序的工具和平台。 无代码平台通过提供预先构建的组件和模块&#xff0c;使得开发人员可以通过简…

王者荣耀java版

主要功能 键盘W,A,S,D键&#xff1a;控制玩家上下左右移动。按钮一&#xff1a;控制英雄发射一个矩形攻击红方小兵。按钮二&#xff1a;控制英雄发射魅惑技能&#xff0c;伤害小兵并让小兵停止移动。技能三&#xff1a;攻击多个敌人并让小兵停止移动。普攻&#xff1a;对小兵造…

初识JVM(简单易懂),解开JVM神秘的面纱

目录 一、什么是JVM&#xff08;Java虚拟机&#xff09;&#xff1f; 二、JVM的功能 三、JVM的功能-即时编译 四、常见的JVM 五、JVM的组成 五、JVM的工作流程 参考资料 一、什么是JVM&#xff08;Java虚拟机&#xff09;&#xff1f; 在Java的世界里&#xff0c;Java虚…

MySQL中自增id用完怎么办?

MySQL中自增id用完怎么办&#xff1f; MySQL里有很多自增的id&#xff0c;每个自增id都是定义了初始值&#xff0c;然后不停地往上加步长。虽然自然数是没有上限的&#xff0c;但是在计算机里&#xff0c;只要定义了表示这个数的字节长度&#xff0c;那它就有上限。比如&#…

如何进行MySQL的主从复制(MySQL5.7)

背景&#xff1a;在一些Web服务器开发中&#xff0c;系统用户在进行数据访问时&#xff0c;基本都是直接操作数据库MySQL进行访问&#xff0c;而这种情况下&#xff0c;若只有一台MySQL服务器&#xff0c;可能会存在如下问题 数据的读和写的所有压力都会由一台数据库独…

postgresql-shared_buffers参数详解

shared_buffers 是 PostgreSQL 中一个非常关键的参数&#xff0c;用于配置服务器使用的共享内存缓冲区的大小。这些缓冲区用于存储数据页&#xff0c;以便数据库可以更快地访问磁盘上的数据。 这个参数在 PostgreSQL 的性能方面有着重要的影响。增加 shared_buffers 可以提高数…

【网络奇缘】- 计算机网络|分层结构|ISO模型

&#x1f308;个人主页: Aileen_0v0&#x1f525;系列专栏: 一见倾心,再见倾城 --- 计算机网络~&#x1f4ab;个人格言:"没有罗马,那就自己创造罗马~" 目录 计算机网络分层结构 OSI参考模型 OSI模型起源 失败原因: OSI模型组成 协议的作用 &#x1f4dd;全文…

阿里入局鸿蒙!鸿蒙原生应用再添两员新丁

今日HarmonyOS微博称&#xff0c;阿里钉钉、蚂蚁集团旗下的移动开发平台mPaaS与华为达成合作&#xff0c;宣布启动鸿蒙原生应用的开发&#xff01;相关应用将以原生方式适配#HarmonyOS NEXT#系统。 #HarmonyOS#市场或迎来爆发式增长&#xff01; 阿里钉钉 阿里钉钉与华为达成合…

每日一题:LeetCode-103/107.二叉树的(层序/锯齿形层序)遍历

每日一题系列&#xff08;day 04&#xff09; 前言&#xff1a; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f50e…

成为AI产品经理——模型构建过程(上)

目录 一、背景 1.对内 2.对外 二、模型构建过程 1.模型设计 2.特征工程 ① 数据清洗 ② 特征提取 数值型数据 标签/描述类数据特征 非结构化数据&#xff08;处理文本特征&#xff09; 网络关系型数据 ③ 特征选择 ④ 训练集/测试集 一、背景 虽然产品经理不…