长春吉林建设信息网站,“哈尔滨企业服务平台”公众号,制作公司网站有哪些,wordpress 附件重命名Meteor Shower S#xff08;流星雨#xff09;
题目连接
题目描述
贝茜听说一场特别的流星雨即将到来#xff1a;这些流星会撞向地球#xff0c;并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑#xff0c;发誓要找到一个安全的地方#xff08;一个永远不会被流星…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 M1 M1 行第 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() {Queuepos 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;}
}
