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

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

试题链接:

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

FPGA----ZCU106使用petalinux 2019.1(全网最详)

一、环境安装 1、软硬件需求&#xff1a;Vivado 2019.1、ZCU106、Ubuntu 18.04.1、petalinux 2019.1 本文基于2019.1版本的UG1144文档构建https://docs.xilinx.com/api/khub/documents/HXzkPWw1pfgmyp8i8JKniQ/content?Ft-Calling-Appft%2Fturnkey-portal&Ft-Calling-Ap…

2023年【起重机械指挥】考试题及起重机械指挥找解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 起重机械指挥考试题考前必练&#xff01;安全生产模拟考试一点通每个月更新起重机械指挥找解析题目及答案&#xff01;多做几遍&#xff0c;其实通过起重机械指挥作业考试题库很简单。 1、【多选题】按照事故造成的人…

线程的几种状态

&#xff08;线程的几种状态&#xff09; 1.线程状态&#xff08;生命周期&#xff09; 1.1.源码中的状态 关于Java线程的状态&#xff0c;网上说法很多&#xff0c;有五种、六种甚至七种&#xff0c;本文采用Java官方的线程状态分类。 实际上&#xff0c;官方一共给出了六种…

攻防世界-web-Confusion1

1. 题目描述 打开链接&#xff0c;如图 点击Login和Rigister&#xff0c;都报错 但是有提示 指出了flag所在的位置&#xff0c;题目中直接能获取到的信息暂时就这么些了 2. 思路分析 既然告诉了我们flag文件的位置&#xff0c;那么要读取到这个文件&#xff0c;要么是任意文…

合并区间问题

以数组 intervals 表示若干个区间的集合&#xff0c;其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间&#xff0c;并返回 一个不重叠的区间数组&#xff0c;该数组需恰好覆盖输入中的所有区间 。 示例 1&#xff1a; 输入&#xff1a;intervals [[1,…

【Vue】自定义指令

hello&#xff0c;我是小索奇&#xff0c;精心制作的Vue系列持续发放&#xff0c;涵盖大量的经验和示例&#xff0c;如果对您有用&#xff0c;可以点赞收藏哈~ 自定义指令 自定义指令就是自己定义的指令&#xff0c;是对 DOM 元素进行底层操作封装 ,程序化地控制 DOM&#xff…

常见面试题-Redis持久化策略

谈谈Redis 的持久化策略&#xff1f; 参考文章&#xff1a; Redis 持久化机制演进与百度智能云的实践 Redis的确是将数据存储在内存的&#xff0c;但是也会有相关的持久化机制将内存持久化备份到磁盘&#xff0c;以便于重启时数据能够重新恢复到内存中&#xff0c;避免数据丢…

数据结构:顺序表

目录 一.顺序表 1.1概念以及结构 1.2动态顺序表实现 1.2.1文件创建&#xff1a; 1.2.2接口实现 1.顺序表打印 2.顺序表初始化 3.顺序表尾插 4.顺序表头插 5.顺序表尾删 6.顺序表头删 7.顺序表在pos位置插入x 8.顺序表删除pos位置的值 9.顺序表销毁 二.顺序表问题 一.…

关于 Docker

关于 Docker 1. 术语Docker Enginedockerd&#xff08;Docker daemon&#xff09;containerdOCI (Open Container Initiative)runcDocker shimCRI (Container Runtime Interface)CRI-O 2. 容器启动过程在 Linux 中的实现daemon 的作用 Docker 是个划时代的开源项目&#xff0c;…

「快学Docker」监控和日志记录容器的健康和性能

「快学Docker」监控和日志记录容器的健康和性能 1. 容器健康状态监控2. 性能监控3. 日志记录几种采集架构图 4. 监控工具和平台cAdvisor&#xff08;Container Advisor&#xff09;PrometheusGrafana 5. 自动化运维 1. 容器健康状态监控 方法1&#xff1a;需要实时监测容器的运…

在iPad pro上安装VSCode,秒变生产力工具提升编程工作效率!

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;网络奇遇记、Cpolar杂谈 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;前言一. 本地环境配置二. 内网穿透2.1 安装cpolar内网穿透(支持一键自动安装脚本)2.…

智慧法院档案数字化解决方案

智慧法院档案数字化解决方案可以采用以下步骤&#xff1a; 1. 确定数字化目标&#xff1a;明确数字化的目标和范围&#xff0c;比如将所有的案件相关文件、纸质档案和材料进行数字化。 2. 确定数字化流程&#xff1a;制定数字化的流程和标准&#xff0c;比如采用哪些设备和软件…

人工智能基础_机器学习047_用逻辑回归实现二分类以上的多分类_手写代码实现逻辑回归OVR概率计算---人工智能工作笔记0087

然后我们再来看一下如何我们自己使用代码实现逻辑回归的,对二分类以上,比如三分类的概率计算 我们还是使用莺尾花数据 首先我们把公式写出来 def sigmoid(z): 定义出来这个函数 可以看看到这需要我们理解OVR是如何进行多分类的,我们先来看这个 OVR分类器 思想 OVR(One-vs-…

Android设计模式--模板方法模式

一&#xff0c;定义 定义一个操作中的算法的框架&#xff0c;而将一些步骤延迟到子类中&#xff0c;使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。 在面向对象的开发过程中&#xff0c;通常会遇到这样一个问题&#xff0c;我们知道一个算法所需的关键步…

2023年【上海市安全员C证】考试及上海市安全员C证找解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2023年上海市安全员C证考试为正在备考上海市安全员C证操作证的学员准备的理论考试专题&#xff0c;每个月更新的上海市安全员C证找解析祝您顺利通过上海市安全员C证考试。 1、【多选题】2017年9月颁发的《中共上海市委…

达索系统SOLIDWORKS流体分析网格划分失败,大多是这2种原因

SOLIDWORKS Flow Simulation 是直观的流体力学 (CFD) 分析软件&#xff0c;该软件功能强大、操作人性化&#xff0c;快速轻松的分析产品内部或外部流体的流动情况&#xff0c;以用来改善产品性能和功能。 当流体分析运行网格划分时&#xff0c;提示失败。 这是由于凸起面与圆…

HTML新手入门笔记整理:HTML基本介绍

网页 静态页面 仅可供用户浏览&#xff0c;不具备与服务器交互的功能。 动态页面 可供用户浏览&#xff0c;具备与服务器交互的功能。 HTML HTML&#xff0c;全称HyperText Markup Language&#xff08;超文本标记语言&#xff09;,是一种用于创建网页的标准标记语言。用于…

基于向量加权平均算法优化概率神经网络PNN的分类预测 - 附代码

基于向量加权平均算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于向量加权平均算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于向量加权平均优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xf…

MySQL 事务的底层原理和 MVCC(二)

7.2. undo 日志 7.2.1. 事务回滚的需求 我们说过事务需要保证原子性&#xff0c;也就是事务中的操作要么全部完成&#xff0c;要么什么也不做。但是偏偏有时候事务执行到一半会出现一些情况&#xff0c;比如&#xff1a; 情况一&#xff1a;事务执行过程中可能遇到各种错误&a…

C语言--数组与指针--打印字符串的n种方式

一.知识背景 一维数组名的含义 arr一般表示数组的起始地址&#xff08;除了两种例外&#xff09; 1.在定义数组的同一个函数中(不是形参),求sizeof(arr),求整个数组的字节数 2.在定义数组的同一个函数中(不是形参),&arr1,加整个数组的大小 (经常考试) 3.除上面以外,arr都表…