题目描述
题目地址：https://vjudge.net/problem/POJ-3669
倒霉蛋Bessie现在坐标原点（0，0），现在要有陨石砸下来，寻找Bessie到达安全地点（陨石砸不到的点）所需的最短时间。
此次共有M (1 ≤ M ≤ 50,000)颗流星来袭，流星i将在时间点Ti (0 ≤ Ti ≤ 1,000) 袭击点 (Xi, Yi) (0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300)。每颗流星都将摧毁落点及其相邻四点的区域。
Bessie在0时刻时处于原点，且只能行于第一象限，以平行与坐标轴每秒一个单位长度的速度奔走于未被毁坏的相邻（通常为4）点上。在某点被摧毁的刹那及其往后的时刻，她都无法进入该点。
Input - 输入
第1行: 一个整数: M
第2..M+1行: 第i+1行包含由空格分隔的三个整数: Xi, Yi, and Ti
Output - 输出
仅一行: Bessie寻得安全点所花费的最短时间，无解则为-1。
样例：
Input:
4
0 0 2
2 1 2
1 1 2
0 3 5
Output:
5
分析：
0时刻 1时刻 2时刻 3时刻 4时刻 5时刻
(0,0)->(0,1)->(0,2)->(0,3)->(0,4)->(0,5)
->(1,3)->(1,4)
->(2,3)
5时刻的三个点是最近的安全点。在纸上画一下就能理解。
题目分析
看到最短就想到bfs。最简单的地图只有两种状态，可达和不可达。
这题稍微复杂的是：
- 判断点是否可达。有一个时间的概念，在某一时刻及该时刻后，某点不可达。
- 不可达点有范围影响。
- 终点（安全点）不是指定地点。
解决思路：
map不用0、1来标记，而是用int t标记。-1代表安全，不会被陨石摧毁;t代表在t时刻被摧毁。- 输入陨石落点时，对上下左右的点也进行标记。
map标记为-1的点就是安全地点，即终点。
细节见代码
代码
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Point {
public int x, y, t;
public Point() {
}
public Point(int x, int y, int t) {
this.x = x;
this.y = y;
this.t = t;
}
}
public class Main {
private static final Scanner SC = new Scanner(System.in);
private static final int[] DX = {0, 0, -1, 1, 0};
private static final int[] DY = {-1, 1, 0, 0, 0};
private static int row = 303, col = 303; // 根据陨石坠落范围[0,300]设置地图范围，大一点点就可以，大太多也没用，因为求的是最短
private static int[][] map = new int[row][col];
/**
* 初始化地图
* 初始化值为-1，代表安全地点
*/
public static void initMap() {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
map[i][j] = -1;
}
}
}
/**
* 记录陨石对地图的破坏情况
*/
public static void recordMeteor() {
int meteors = SC.nextInt();
int r, c, t, tr, tc;
// 记录陨石击中的时间
while (meteors-- > 0) {
// r,c为坐标
r = SC.nextInt();
c = SC.nextInt();
// t为陨石最早击中的时刻（最早摧毁时间）
// 部分地点会被重复摧毁，在该点被摧毁的刹那及其往后的时刻，都不能再到达，所以要保留最早摧毁时间
t = SC.nextInt();
// 陨石有溅射效果，落点和上下左右，共5个点都会被摧毁
for (int i = 0; i < 5; i++) {
tr = r + DX[i];
tc = c + DY[i];
// 陨石也有可摧毁的范围
if (tr < 0 || tr > 301 || tc < 0 || tc > 301) {
continue;
}
if (map[tr][tc] == -1) {
map[tr][tc] = t;
} else {// 保留最早被摧毁的时间
map[tr][tc] = Math.min(map[tr][tc], t);
}
}
}
}
public static int bfs() {
// 天胡，起点就是安全的
if (map[0][0] == -1) {
return 0;
}
// 反向天胡，没来及跑就被炸了
if (map[0][0] == 0) {
return -1;
}
Queue<Point> queue = new LinkedList<Point>();
queue.add(new Point(0, 0, 0));
while (!queue.isEmpty()) {
Point cur = queue.poll();
int tr, tc;
// 安全了，返回
if (map[cur.x][cur.y] == -1) {
return cur.t;
}
// 当前点不可达，抛弃这个状态
if (map[cur.x][cur.y] <= cur.t) {
continue;
}
// 当前点可达，但是还得跑
for (int i = 0; i < 4; i++) {
tr = cur.x + DX[i];
tc = cur.y + DY[i];
if (0 <= tr && tr < row && 0 <= tc && tc < col) {
// 下一步是安全地点
if (map[tr][tc] == -1) {
return cur.t + 1;
}
// 下一步可以到达，但是还得接着跑
if (cur.t < map[tr][tc]) {
// 把来时的路炸了，不走回头路
map[cur.x][cur.y] = cur.t;
queue.add(new Point(tr, tc, cur.t + 1));
}
}
}
}
return -1;
}
public static void main(String[] args) {
// 初始化地图
initMap();
// 记录陨石对地图的破坏情况
recordMeteor();
// bfs
int ans = bfs();
System.out.println(ans);
}
}
参考
- https://blog.csdn.net/queque_heiya/article/details/104086766
- https://blog.csdn.net/a1097304791/article/details/101617157
- https://www.cnblogs.com/sky-stars/p/11185040.html
- https://www.cnblogs.com/demian/p/6152963.html
大佬们都是C/C++