搜索-BFS Meteor Shower S（流星雨）

Meteor Shower S（流星雨）

题目连接

题目描述

贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。

如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。

根据预报，一共有 $M$ 颗流星 $(1\le M\le 50,000)$ 会坠落在农场上，其中第 $i$ 颗流星会在时刻 $T_i$（$0\le T_i\le 1000$）砸在坐标为 $(X_i,Y_i)(0\le X_i\le 300$，$0\le Y_i\le 300)$ 的格子里。流星的力量会将它所在的格子，以及周围 $4$ 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。

贝茜在时刻 $0$ 开始行动，她只能在第一象限中，平行于坐标轴行动，每 $1$ 个时刻中，她能移动到相邻的（一般是 $4$ 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 $t$ 被流星撞击或烧焦，那么贝茜只能在 $t$ 之前的时刻在这个格子里出现。 贝茜一开始在 $(0,0)$。

请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 $-1$。

输入格式

共 $M+1$ 行，第 $1$ 行输入一个整数 $M$，接下来的 $M$ 行每行输入三个整数分别为 $X_i,Y_i,T_i$。

输出格式

贝茜到达安全地点所需的最短时间，如果不可能，则为 $-1$。

样例 #1

样例输入 #1

4
0 0 2
2 1 2
1 1 2
0 3 5

样例输出 #1

5

题解

思路

这道题如果找到方向就会很快解决，我自己也是写的特别复杂，最后看了别的大佬的思路，又重新写了一遍。
首先我们可以确定每一步的状态，无非就是其坐标以及到达的时间。
题目告诉了流星到达的时间以及到达的位置，所以我们可以把最后不可达的位置处理出来，也就是说一个二维数组，表示所有的点，数组的值就是流星到达的最短时间，如果贝茜到达某一点的时间小于该点流星到达的最早时间，那么就一定是合法的状态，就可以加入到队列中，如果到达的地方没有流星波及，也就是说该点的值是初始的值，那么这个点一定就是安全的地方，又由于我们是BFS，那么就一定是正确答案。所有的状态都走完之后，没有结果就返回-1。

细节：

1. 在初始化的时候一点要注意边界问题，以及每次都去最小的，因为题目的输入顺序并不是按照时间递增的。
2. 题目的输入也可能数组相同的坐标不同的时间。

代码实现

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;}
}