搜索-BFS Meteor Shower S(流星雨)
Meteor Shower S(流星雨)
题目连接
题目描述
贝茜听说一场特别的流星雨即将到来:这些流星会撞向地球,并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑,发誓要找到一个安全的地方(一个永远不会被流星摧毁的地方)。
如果将牧场放入一个直角坐标系中,贝茜现在的位置是原点,并且,贝茜不能踏上一块被流星砸过的土地。
根据预报,一共有 M M M 颗流星 ( 1 ≤ M ≤ 50 , 000 ) (1\leq M\leq 50,000) (1≤M≤50,000) 会坠落在农场上,其中第 i i i 颗流星会在时刻 T i T_i Ti( 0 ≤ T i ≤ 1000 0 \leq T _ i \leq 1000 0≤Ti≤1000)砸在坐标为 ( X i , Y i ) ( 0 ≤ X i ≤ 300 (X_i,Y_i)(0\leq X_i\leq 300 (Xi,Yi)(0≤Xi≤300, 0 ≤ Y i ≤ 300 ) 0\leq Y_i\leq 300) 0≤Yi≤300) 的格子里。流星的力量会将它所在的格子,以及周围 4 4 4 个相邻的格子都化为焦土,当然贝茜也无法再在这些格子上行走。
贝茜在时刻 0 0 0 开始行动,她只能在第一象限中,平行于坐标轴行动,每 1 1 1 个时刻中,她能移动到相邻的(一般是 4 4 4 个)格子中的任意一个,当然目标格子要没有被烧焦才行。如果一个格子在时刻 t t t 被流星撞击或烧焦,那么贝茜只能在 t t t 之前的时刻在这个格子里出现。 贝茜一开始在 ( 0 , 0 ) (0,0) (0,0)。
请你计算一下,贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 − 1 −1 −1。
输入格式
共 M + 1 M+1 M+1 行,第 1 1 1 行输入一个整数 M M M,接下来的 M M M 行每行输入三个整数分别为 X i , Y i , T i X_i, Y_i, T_i Xi,Yi,Ti。
输出格式
贝茜到达安全地点所需的最短时间,如果不可能,则为 − 1 -1 −1。
样例 #1
样例输入 #1
4
0 0 2
2 1 2
1 1 2
0 3 5
样例输出 #1
5
题解
思路
这道题如果找到方向就会很快解决,我自己也是写的特别复杂,最后看了别的大佬的思路,又重新写了一遍。
首先我们可以确定每一步的状态,无非就是其坐标以及到达的时间。
题目告诉了流星到达的时间以及到达的位置,所以我们可以把最后不可达的位置处理出来,也就是说一个二维数组,表示所有的点,数组的值就是流星到达的最短时间,如果贝茜到达某一点的时间小于该点流星到达的最早时间,那么就一定是合法的状态,就可以加入到队列中,如果到达的地方没有流星波及,也就是说该点的值是初始的值,那么这个点一定就是安全的地方,又由于我们是BFS,那么就一定是正确答案。所有的状态都走完之后,没有结果就返回-1。
细节:
- 在初始化的时候一点要注意边界问题,以及每次都去最小的,因为题目的输入顺序并不是按照时间递增的。
- 题目的输入也可能数组相同的坐标不同的时间。
代码实现
import java.util.*;public class Main {static final int N = 310, INF = 0x3f3f3f3f;static boolean[][] st = new boolean[N][N];static int[][] w = new int[N][N];static int[][] dir = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};static int n;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();for(int i = 0; i < N; i ++){Arrays.fill(w[i],INF);}// 处理处理每个合法的位置流星最早到达且波及的时间for (int i = 0; i < n; i++) {int x = in.nextInt();int y = in.nextInt();int t = in.nextInt();w[x][y] = Math.min(w[x][y], t);for (int j = 0; j < 4; j++) {int dx = x + dir[j][0];int dy = y + dir[j][1];if (dx >= 0 && dy >= 0) {w[dx][dy] = Math.min(w[dx][dy], t);}}}int res = bfs();System.out.println(res);}public static int bfs() {Queue<pos> q = new ArrayDeque<>();pos p = new pos(0, 0, 0);q.add(p);st[0][0] = true;while(!q.isEmpty()) {p = q.poll();for (int j = 0; j < 4; j++) {int x = p.x + dir[j][0];int y = p.y + dir[j][1];int t = p.t + 1;if (x >= 0 && y >= 0) {// 说明流星不会影响,直接返回结果if (w[x][y] == INF) return t;// 到达从未的地方时比流星到达的时间晚if(t < w[x][y] && !st[x][y]){q.add(new pos(x, y, t));st[x][y] = true;}}}}return -1;}
}
class pos{int x;int y;int t;public pos(int x, int y, int t) {this.x = x;this.y = y;this.t = t;}
}
相关文章:
搜索-BFS Meteor Shower S(流星雨)
Meteor Shower S(流星雨) 题目连接 题目描述 贝茜听说一场特别的流星雨即将到来:这些流星会撞向地球,并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑,发誓要找到一个安全的地方(一个永远不会被流星…...
RabbitMQ实战:Springboot集成RabbitMQ并验证五种消息模型
这目录 一、添加依赖二、配置文件中添加RabbitMQ访问配置三、消息生产者代码四、消息消费者代码五、验证参考资料 一、添加依赖 <!--AMQP依赖,包含RabbitMQ--><dependency><groupId>org.springframework.boot</groupId><artifactId>s…...

配置与管理防火墙
配置与管理防火墙 1,概念:设置在不同网络或网络安全域之间的一系列部件的组合。 2,功能:保护内网中易手攻击的服务;控制内外网之间网络系统的访问;隐藏内网的IP地址及结构的细节,提高网络保护…...

【SpringBoot】-- 实现本地文件/图片上传到服务器生成url地址
在java项目中你可能会有以下需求:用户上传本地图片,然后展示在网页上。本篇文章将使用阿里云oss实现上传图片到oss,oss生成url。 一、准备工作 首先进入阿里云,按如下操作 进入创建页面,修改读写权限为公共读 然后进…...

计算机基础专升本笔记十四-计算机网络基础(一)
计算机基础专升本笔记十四-计算机网络基础(一) 一、计算机网络的发展历程 第一代计算机网络(数据通信) 以数据通信为主的第一代计算机网络。主要是指美国军方用于防控系统的一种联机系统。它只是计算机网络的雏形。 第二代计算…...
【华为OD机试】转盘寿司【C卷|100分】
【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述 寿司店周年庆,正在举办优惠活动回馈新老客户。 寿司转盘上总共有 n 盘寿司,prices[i] 是第 i 盘寿司的价格, 如果客户选择了第 i 盘寿司,寿司店免费赠送客户距离第 i 盘寿司最近的下一…...
使用Node JS获取WI-FI密码
演示效果 全局安装wifi-password-cli依赖 shell 复制代码 npm install wifi-password-cli -g # or npx wifi-password-cli 使用 shell 复制代码 $ wifi-password [network-name] $ wifi-password 12345678 $ wifi-password 办公室wifi a1234b2345 觉得Node.js很神奇是…...
先缓存第二集抖音接入 ,最近加班猛,就分享简单的知识,如何使用:关于使用replace的用法正则表达式
1、需求:比如在cocos creator策划让你制作一个预制体,标题要读取配置,然后中间显示的内容要滚动的,要做成一个通用的,然后给到的配置表是这样子的: 配置表:假设字段是这样子的 content "内容标题&…...

企微hook源码
企微hook源码已经在QQ群内开源。速度进群下载,避免和谐。 QQ群:649480745...

vsphere虚拟机迁移是灰色如何解决
vsphere虚拟机迁移是灰色如何解决 问题描述: 在vsphere中,迁移虚拟机时迁移按钮是灰色,无法迁移,关机之后也无法迁移 虚拟机按钮为灰色 找到虚拟机存储对应的位置,查询是否有.vmx虚拟机文件 查询中发现有.vmx文件存…...
swift 闭包捕获列表
以下函数会打印出什么? var car "Benz" let closure { [car] in print("I drive \(car)") } car "Tesla" closure() 因为 clousre 已经申明将 car 复制进去了([car]),此时clousre 里的 car…...

JavaWeb04-Request,Response
目录 一、Request(请求) 1.作用 2.继承体系 3.获取请求数据 (1)请求行 (2)请求头 (3)请求体(POST) (5)Request通用方式获取请求…...

使用 Docker 部署 Fiora 在线聊天室平台
一、Fiora 介绍 Fiora 简介 Fiora 是一款开源免费的在线聊天系统。 GitHub:https://github.com/yinxin630/fiora Fiora 功能 注册账号并登录,可以长久保存你的数据加入现有群组或者创建自己的群组,来和大家交流和任意人私聊,并添…...

Unity Samples和帧动画的问题
拖动序列帧图片和自己创建clip的帧率不同 我今天在创建帧动画的时候用了两种方式第一种是直接拖动序列帧图片到Hierachy,然后生成的第二种是这样我发现两者播放的动画速率不一样最后查了半天查不到原因。最后发现是Samples的原因,而且Unity把Samples这个…...

几何工具的使用
Geometry - Creation 创建几何 CogCreateCircleTool:创建圆CogCreateEllipseTool:创建椭圆CogCreateLineBisectPointsTool:带有两个点的平行线CogCreateLineParallelTool:在某一点创建某条线的平行线CogCreateLinePerpendicularTool:在某一点创建某条线…...

sudo command not found
文章目录 一句话Intro其他操作 一句话 sudo 某命令 改成 sudo -i 某命令 试试。 -i 会把当前用户的环境变量带过去,这样在sudo的时候,有更高的权限,有本用户的环境变量(下的程序命令)。 -i, --login run login shell as the target user; a …...

1.【Labview白话系列】Labview数组精讲
题主经过写文章一段时间的发现,许多同学对该软件的理解和编程能力是不太一样的,有些知识相对一些同学较为简单,但是有些同学提问就比较困难。那么针对这个问题,题主打算出一期说白话系列的专栏,在该栏目中用最通俗的大…...

ANTLR4规则解析生成器(三):遍历语法分析树
文章目录 1 词法分析2 语法分析3 遍历语法分析树3.1 Listener3.2 Visitor 4 总结 1 词法分析 词法分析就是对给定的字符串进行分割,提取出其中的单词。 在antlr4中,词法规则的名称的首字母需要大写,右侧必须是终结符,通常将词法…...

OpenCV实现目标追踪
目录 准备工作 语言: 软件包: 效果演示 代码解读 (1)导入OpenCV库 (2)使用 cv2.VideoCapture 打开指定路径的视频文件 (3)使用 vid.read() 读取视频的第一帧,ret…...

【剑指offer--C/C++】JZ6 从尾到头打印链表
一、题目 二、本人思路及代码 直接在链表里进行翻转不太方便操作,但是数组就可以通过下标进行操作,于是, 思路1、 先遍历链表,以此存到vector中,然后再从后往前遍历这vector,存入到一个新的vector,就完成…...

华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...

04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving
地址:LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂,正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...