搜索-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,就完成…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
[USACO23FEB] Bakery S
题目描述 Bessie 开了一家面包店! 在她的面包店里,Bessie 有一个烤箱,可以在 t C t_C tC 的时间内生产一块饼干或在 t M t_M tM 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC,tM≤109)。由于空间…...
Web APIS Day01
1.声明变量const优先 那为什么一开始前面就不能用const呢,接下来看几个例子: 下面这张为什么可以用const呢?因为复杂数据的引用地址没变,数组还是数组,只是添加了个元素,本质没变,所以可以用con…...
记一次spark在docker本地启动报错
1,背景 在docker中部署spark服务和调用spark服务的微服务,微服务之间通过fegin调用 2,问题,docker容器中服务器来后,注册中心都有,调用服务也正常,但是调用spark启动任务后报错,报错…...
