搜索-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,就完成…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
