0 0 投票数

g[x][y][t] 表示点 (x, y) 在时刻 t 可以踩上去，visited[x][y][t] 记录三元组的访问状态。

import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

static boolean[][][] g; // 点 (x, y) 在时刻 t 是否可达
static boolean[][][] visited; // 标记访问状态
static int n;
static int m;
static int d;

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
int k = in.nextInt();
d = in.nextInt();
g = new boolean[n + 1][m + 1][d + 1];
visited = new boolean[n + 1][m + 1][d + 1];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m ;j++)
for (int l = 0; l <= d; l++)
g[i][j][l] = true; // 默认都可以访问
for (int i = 0; i < k; i++) {
String c = in.next();
int t = in.nextInt();
int v = in.nextInt();
int x = in.nextInt();
int y = in.nextInt();
// 守卫所在的点永远不可达
for (int j = 0; j <= d; j++) {
g[x][y][j] = false;
}
// 获取射击方向
int dx = 0, dy = 0;
switch (c) {
case "N":
dx = -1;
break;
case "S":
dx = 1;
break;
case "W":
dy = -1;
break;
case "E":
dy = 1;
break;
}
int p = 1;
// 计算子弹到达的点及到达的时间，在该时刻该点不可达
while (p <= d) {
int newX = x + dx * v * p;
int newY = y + dy * v * p;
// 计算第一颗子弹命中的位置
if (newX >=0 && newX <= n && newY >=0 && newY <= m) {
g[newX][newY][p] = false;
int l = 1;
while (p + l * t <= d) {
// 该位置每隔 t 秒命中一次
g[newX][newY][p + l * t] = false;
l++;
}
}
p++;
}
}
// 预处理完成，开始广搜，输出答案
int ans = bfs(0, 0, 0);
System.out.println(ans == -1 ? "Bad luck!" : ans);
in.close();
}

private static int bfs(int X, int Y, int T) {
visited[X][Y][T] = true;
while (!q.isEmpty()) {
Point current = q.poll();
// 在生命耗尽之前到达出口
if (current.getX() == n && current.getY() == m && current.getT() <= d) {
return current.getT();
} else if (current.getT() > d){
// 耗时大于生命，直接死掉
return -1;
} else {
for (Point neighbour : getNeighbours(current)) {
visited[neighbour.getX()][neighbour.getY()][neighbour.getT()] = true;
}
}
}
// 走投无路，死掉
return -1;
}

private static ArrayList<Point> getNeighbours(Point p) {
ArrayList<Point> neighbours = new ArrayList<Point>();
int x = p.getX();
int y = p.getY();
int t = p.getT();
for (int dx = -1; dx <= 1; dx++)
for (int dy = -1; dy <= 1; dy++) {
// 可以站在原地等 1 秒，找子弹的空隙，所以一共是 5 个邻居
if (Math.abs(dx) != Math.abs(dy) || dx == 0 && dy == 0) {
int xx = x + dx;
int yy = y + dy;
// t + 1 > d 的全部剪枝
if (xx >= 0 && xx <= n && yy >= 0 && yy <= m && t + 1 <= d) {
if (g[xx][yy][t + 1])
if (!visited[xx][yy][t + 1])
neighbours.add(new Point(xx, yy, t + 1));
}
}
}
return neighbours;
}
}

class Point {
private int x;
private int y;
private int t;

public Point(int x, int y, int t) {
super();
this.x = x;
this.y = y;
this.t = t;
}

public int getX() {
return x;
}

public int getY() {
return y;
}

public int getT() {
return t;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + t;
result = prime * result + x;
result = prime * result + y;
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Point other = (Point) obj;
if (t != other.t)
return false;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}

@Override
public String toString() {
return "Point [x=" + x + ", y=" + y + ", t=" + t + "]";
}

}
0 0 投票数

（可选）如果您也有个人网站，不妨分享一下

0 评论