搜索-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,就完成…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...

2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...