蓝桥杯:染色时间

news/2024/3/29 6:24:28/文章来源:https://blog.csdn.net/qq_32468603/article/details/129248626

蓝桥杯:染色时间https://www.lanqiao.cn/problems/2386/learning/?contest_id=80

问题描述

输入格式

输出格式

样例输入输出

样例输入

样例输出

评测用例规模与约定

解题思路:优先队列

AC代码(Java):


问题描述

        小蓝有一个 n 行 m 列的白色棋盘, 棋盘的每一个方格都可以被染成彩色。

        每个方格有一个染色时间{\color{Red} Tij}​, 不同方格的染色时间可能不同。如果一个方 格被触发了染色, 这个方格就会在 {\color{Red} Tij}秒之后变成彩色, 然后将自己上下左右四 个方向相邻的方格触发染色。每个方格只能被触发染色一次, 第一次触发之后 的触发为无效触发。

        给定每个方格的染色时间, 在时刻 0 触发第一行第一列的方格染色, 请问 多长时间后整个棋盘完成染色。

输入格式

        输入的第一行包含两个整数 n,m, 分别表示棋盘的行数和列数。

        接下来 n 行, 每行 m 个正整数, 相邻的整数之间用一个空格分隔, 表示每 个方格的染色时间。该部分的第 i 行第 j 个整数表示 {\color{Red} Tij}​, 即第 i 行第 j 列的方 格的染色时间。

输出格式

         输出一行包含一个整数, 表示整个棋盘完成染色的时间。

样例输入输出

样例输入


2 31 2 34 5 6

样例输出

12

评测用例规模与约定

对于 30% 的评测用例, 1≤n,m≤10 。

对于 60% 的评测用例, 1≤n,m≤50 。

对于所有评测用例, 1≤n,m≤500,1≤{\color{Red} Tij}​≤1000 。

解题思路:优先队列

        首先我们分析一下,题目要求我们从0,0处开始染色,也就是我们让0,0开始染色的时候,它的上下左右四个方向所有使用的时间为 自身染色时间+0,0处的染色时间,如:

将0,0处染色之后,图中染色时间分布情况:
0 3 3
4 5 6

        我们知道,0,1处染色时间3肯定是要比1,0处染色时间快的,所以当0,1处染色完成,应该是这样的:

将0,1处染色之后,图中染色时间分布情况:
0 0 6
4 8 6

        其实这里就可以看出来了,可以依次将染色的点存入队列之中,每次取出耗时最短的点,然后将其上下左右四个位置加上自身染色所需要的时间即可。

        所以这道题可以用优先队列来做,我们定义一个类(结构体)Node,该类存放有三个属性,分别是x(行),y(列),time(染色累计耗时)。

   static class Node{int x;int y;int time; //耗时public Node(int x,int y,int time){this.x = x;this.y = y;this.time = time;}}

        这样我们就可以将0,0处节点的信息存放到优先队列中,每次我们取出耗时最短的一个节点,y也就是先完成染色的节点先出来,然后将其染色累计耗时,添加到上下左右四个还没有染色的节点中(如果染色了,我们就将对应位置的节点的值设置为0,方便判断)。

        依次再存入节点中,这样每次取出一个完成染色的节点,并且向四周开始没有染色的节点染色,这样优先队列中的最后一个节点就是我们完成染色所需要的时间。

AC代码(Java):

        因为使用Scanner只通过了80%,但是这道题的思路应该就是优先队列不会错,所以我将输入流换成了StreamTokenizer,提高读取性能,才全部通过。

        关于输入输出流性能,可以看:JAVA 输入输出优化

import java.io.*;
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static class Node{int x;int y;int time; //耗时public Node(int x,int y,int time){this.x = x;this.y = y;this.time = time;}}static int[][] dires = {{-1,0},{0,-1},{1,0},{0,1}}; //四个方向,上,右,下,左//优化输入流static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));public static  int nextInt() throws IOException {st.nextToken();return (int) st.nval;}public static void main(String[] args) throws IOException{//在此输入您的代码...int n = nextInt();int m = nextInt();int[][] map = new int[n][m];for(int i = 0;i<n;i++){for(int j = 0;j<m;j++)map[i][j] = nextInt();}//首先队列,每次耗时最短的节点先出队,最后出队的就是耗时最久的PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2)->(n1.time-n2.time)); //升序排序pq.add( new Node(0,0,map[0][0]) );//令该处为0,代表这个位置已经染色过了map[0][0] = 0;int ans = 0;while(!pq.isEmpty()){Node node = pq.poll();//将node节点上下左右的节点入队,并修改自己为 0,代表该节点已经染色for(int[] dire : dires){int x = node.x+dire[0];int y = node.y+dire[1];if(x>=0 && x<n && y>=0 && y<m && map[x][y]!=0){pq.add(new Node(x,y,map[x][y]+node.time));//令该处为0,代表这个位置已经染色过了map[x][y] = 0;}}//该位置已经染色map[node.x][node.y] = 0;ans = node.time;}System.out.println(ans);}
}

        

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

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

相关文章

std::chrono笔记

文章目录1. radio原型作用示例2. duration原型&#xff1a;作用示例3. time_point原型作用示例4. clockssystem_clock示例steady_clock示例high_resolution_clock先说感觉&#xff0c;这个库真恶心&#xff0c;刚接触感觉跟shi一样&#xff0c;特别是那个命名空间&#xff0c;太…

vue2 diff算法

diff是什么 diff 算法是一种通过同层的树节点进行比较的高效算法 其有两个特点&#xff1a; ♥比较只会在同层级进行, 不会跨层级比较 ♥在diff比较的过程中&#xff0c;循环从两边向中间比较 diff 算法的在很多场景下都有应用&#xff0c;在 vue 中&#xff0c;作用于虚拟 dom…

预备2-CMD常用命令

CMD常用命令 先学简单常用的, 其余的要用在学 打开Cmd窗口 Win键R> 输入Cmd回车鼠标点击开始 > 附件>Cmd打开一个窗口,在地址栏输入cmd 操作目录 1.dir 查询当前目录有哪些文件 2.cd.. 上一级目录 3.cd e: 切换到E盘 4.d: 直接去d盘 5.cd /d e:abc 直接去E盘的abc目…

2023年房地产行业研究报告

第一章 行业发展概况 房地产业是指以土地和建筑物为经营对象&#xff0c;从事房地产开发、建设、经营、管理以及维修、装饰和服务的集多种经济活动为一体的综合性产业&#xff0c;是具有先导性、基础性、带动性和风险性的产业。主要包括&#xff1a;土地开发&#xff0c;房屋的…

解决AAC音频编码时间戳的计算问题

1.主题音频是流式数据&#xff0c;并不像视频一样有P帧和B帧的概念。就像砌墙一样&#xff0c;咔咔往上摞就行了。一般来说&#xff0c;AAC编码中生成文件这一步&#xff0c;如果使用的是OutputStream流写入文件的话&#xff0c;就完全不需要计算时间。但在音视频同步或者使用A…

debian 部署nginx https

我是flask 处理请求单进程&#xff0c; 差点意思 &#xff0c; 考虑先flask 在往下走 一&#xff1a;安装nginx 因为我是debian 系统&#xff0c;所以我的建议是直接 sudo apt-get install nginx 你也可以选择在官网下载&#xff0c; 但是我搭建ssl 的时候安装openssl非常的麻…

【无标题】(2019)NOC编程猫创新编程复赛小学组真题含参考

&#xff08;2019&#xff09;NOC编程猫创新编程复赛小学组最后6道大题。前10道是选择填空题 略。 这道题是绘图题&#xff0c;没什么难度&#xff0c;大家绘制这2个正十边形要注意&#xff1a;一是不要超出舞台&#xff1b;二是这2个正十边形不要相交。 这里就不给出具体程序了…

数睿通2.0数据服务功能模块发布

文章目录引言API 目录API 权限API 日志结语引言 数睿通 2.0 之前基本完成了数据集成和数据开发两大模块&#xff0c;也因此得到了一些朋友的帮助和支持&#xff0c;在此由衷的表示感谢&#xff0c;你们的支持便是我们更新的最大动力&#xff01; 目前&#xff0c;数据服务模块…

色环电阻的阻值如何识别

这种是色环电阻&#xff0c;其外表有一圈圈不同颜色的色环&#xff0c;现在在一些电器和电源电路中还有使用。下面的两种色环电阻它颜色还不一样&#xff0c;一个蓝色&#xff0c;一个土黄色&#xff0c;其实这个蓝色的属于金属膜色环电阻&#xff0c;外表涂的是一层金属膜&…

狂神说:面向对象(三)——多态

多态// 对象能执行什么方法&#xff0c;主要看对象左边的类型&#xff0c;和右边的没有关系多态&#xff1a;同一方法可以根据发送对象的不同而采用不同的行为方式父类&#xff1a;public class Person {public void run(){System.out.println("Person > run");}}…

【并发编程学习篇】深入理解CountDownLatch

一、CountDownLatch介绍 CountDownLatch&#xff08;闭锁&#xff09;是一个同步协助类&#xff0c;允许一个或多个线程等待&#xff0c;直到其他线程完成操作集。CountDownLatch使用给定的计数值&#xff08;count&#xff09;初始化。await方法会阻塞直到当前的计数值被coun…

只需四步,手把手教你打造专属数字人

伴随ChatGPT的问世&#xff0c;在技术与商业运作上都日渐发展成熟的数字人产业正持续升温。去年9月&#xff0c;北京市发布了国内首个数字人产业专项支持政策&#xff0c;提出将依托国家文化专网将数字人纳入文化数据服务平台。以数字人、ChatGPT为代表的互联网3.0创新应用产业…

kali下安装Volatility

一、About Volatility Volatility是一款开源内存取证框架&#xff0c;能够对导出的内存镜像进行分析&#xff0c;通过获取内核数据结构&#xff0c;使用插件获取内存的详细情况以及系统的运行状态。 Volatility是一款非常强大的内存取证工具,它是由来自全世界的数百位知名安全…

FAST‘23《λ-IO: A Unified IO Stack for Computational Storage》论文解读

FAST’23《λ-IO: A Unified IO Stack for Computational Storage》论文解读 Data:2023-2-27 Ref: Z. Yang et al., “λ-IO: A Unified IO Stack for Computational Storage,” in 21st USENIX Conference on File and Storage Technologies (FAST 23), Santa Clara, CA, Feb.…

数据可视化第二版-03部分-06章-比较与排序

文章目录数据可视化第二版-03部分-06章-比较与排序总结可视化视角-比较与排序代码实现创建虚拟环境1. python版本管理2.切换到指定版本后安装虚拟环境切换路径到文件当前路径柱形图环形柱状图子弹图哑铃图雷达图词云图教材截图数据可视化第二版-03部分-06章-比较与排序 总结 …

Java 多线程 --- 多线程的相关概念

Java 多线程 --- 多线程的相关概念Race Condition 问题并发编程的性质 --- 原子性, 可见性, 有序性上下文切换 (Context Switch)线程的一些故障 --- 死锁, 活锁, 饥饿死锁 (Deadlock)活锁(Livelock)死锁和活锁的区别饥饿(Starvation)背景: 操作系统 — 线程/进程 同步 Race Co…

【unity学习记录】Canvas Group组件

&#x1f497; 未来的游戏开发程序媛&#xff0c;现在的努力学习菜鸡 &#x1f4a6;本专栏是我关于游戏开发的学习笔记 &#x1f236;本篇是unity的Canvas Group组件 Canvas Group画布组介绍详解1. Alpha2. Interactable3. Blocks Raycasts4. Ignore Parent Groups介绍 画布组…

6.0.4:GrapeCity Documents for Excel GcExcel Crack

在更短的时间内生成 Excel 电子表格&#xff0c;不依赖于 Excel&#xff01; 在任何应用程序中转换、计算、格式化和解析电子表格。 快速高效&#xff1a;其轻巧的尺寸意味着 Documents for Excel 针对快速处理大型 Excel 文档进行了优化 使用适用于 Windows、Linux 和 Mac 的…

JVM 学习(2)—简单理解强、软、弱、虚 Java 四大引用

一、Java 引用概述 Java 中出现四种引用是为了更加灵活地管理对象的生命周期&#xff0c;以便在不同场景下灵活地处理对象的回收问题。不同类型的引用在垃圾回收时的处理方式不同&#xff0c;可以用来实现不同的垃圾回收策略。Java 目前将其分成四类&#xff0c;类图如下&…

mysql一两种索引方式hash和btree

1. Hash索引&#xff1a; Hash 索引结构的特殊性&#xff0c;其检索效率非常高&#xff0c;索引的检索可以一次定位&#xff0c;不像B-Tree 索引需要从根节点到枝节点&#xff0c;最后才能访问到页节点这样多次的IO访问&#xff0c;所以 Hash 索引的查询效率要远高于 B-Tree 索…