結果
| 問題 |
No.5015 Escape from Labyrinth
|
| コンテスト | |
| ユーザー |
 Yu_212
|
| 提出日時 | 2023-04-16 14:03:18 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 17,610 bytes |
| コンパイル時間 | 6,707 ms |
| コンパイル使用メモリ | 94,892 KB |
| 実行使用メモリ | 71,292 KB |
| スコア | 41,530 |
| 最終ジャッジ日時 | 2023-04-16 14:04:38 |
| 合計ジャッジ時間 | 75,550 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 99 WA * 1 |
ソースコード
import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.Collectors;
public class Main {
static boolean isLocal;
Random rand = new Random();
In in = new In(System.in);
PrintStream out = System.out;
long inf = 0x1fffffffffffffffL;
int iinf = 0x3fffffff;
long startTime;
public static final int N = 60;
public int D;
public static final int H = 1500;
public int M;
public int J;
public char[] grid;
public Pos[] ps;
public int[] ds;
public Pos[] jps;
int[] distances;
int[][] route;
boolean[][] beam = new boolean[60][N * N];
int[] avgWait = new int[N * N];
int[] jid = new int[N * N];
public static final String[] ss = {"M L", "M U", "M R", "M D", "S"};
long solve(int seed) {
startTime = System.currentTimeMillis();
in();
distances = new int[(J+3) * (J+3)];
route = new int[(J+3) * (J+3)][];
Arrays.fill(distances, iinf);
for (int i = 0; i < M; i++) {
for (int d = 0; d < 4; d++) {
Pos cur = ps[i];
while (true) {
cur = cur.moved((d+2)%4);
if (cur == null || grid[cur.z] == '#') {
break;
}
for (int j = 0; j < 60; j += ds[i]) {
beam[j][cur.z] = true;
}
}
}
}
for (int i = 0; i < N * N; i++) {
int c = 1;
for (int j = 0; j < 60; j++) {
if (beam[j][i]) {
c++;
} else {
c = 1;
}
avgWait[i] += c;
}
}
for (int i = 0; i < J + 3; i++) {
calcDist(i);
}
int tt = 0;
int cur = J;
BitSet visited = new BitSet(J + 3);
visited.set(J + 2);
tt = moveTo(J, J+1, tt, visited);
visited.clear(J + 2);
tt = moveTo(J+1, J+2, tt, visited);
debug(totalCost);
return 0;
}
int totalCost = 0;
int moveTo(int s, int g, int tt, BitSet visited) {
int cur = s;
visited.set(s);
while (cur != g) {
int md = iinf;
int mi = -1;
for (int i = 0; i < J + 3; i++) {
if (visited.get(i)) {
continue;
}
// debug(i, cur, jps[i].dist(jps[g]), distances[cur * (J + 3) + i]);
int d = distances[cur * (J + 3) + i] + jps[i].dist(jps[g]) * 50;
if (md > d) {
md = d;
mi = i;
}
}
visited.set(mi);
// debug(cur, mi, md, distances[cur * (J + 3) + mi], jps[mi].dist(jps[g]), g);
Pos p = jps[cur];
for (int v : route(jps[cur], jps[mi], tt)) {
if (v < 4) p = p.moved(v);
tt = (tt + 1) % 60;
if (beam[tt][p.z]) {
totalCost += D;
}
totalCost++;
out.println(ss[v]);
}
cur = mi;
}
return tt;
}
List<Integer> route(Pos s, Pos g, int tt) {
class S {
private final Pos p;
private final int t;
private final int d;
public S(Pos p, int t, int d) {
this.p = p;
this.t = t;
this.d = d;
}
}
PriorityQueue<S> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d));
queue.add(new S(s, tt, 0));
int[][] dist = new int[60][N * N];
int[][] prev = new int[60][N * N];
for (int i = 0; i < 60; i++) {
Arrays.fill(dist[i], iinf);
Arrays.fill(prev[i], -1);
}
dist[tt][s.z] = 0;
while (!queue.isEmpty()) {
S v = queue.remove();
if (dist[v.t][v.p.z] < v.d) {
continue;
}
if (v.p.z == g.z) {
List<Integer> route = new ArrayList<>();
Pos cur = v.p;
int ct = v.t;
while (prev[ct][cur.z] != -1) {
route.add(prev[ct][cur.z]);
if (prev[ct][cur.z] < 4) {
cur = cur.moved((prev[ct][cur.z] + 2) % 4);
}
ct = (ct + 59) % 60;
}
Collections.reverse(route);
return route;
}
int nt = (v.t + 1) % 60;
for (int d = 0; d < 4; d++) {
Pos q = v.p.moved(d);
if (q == null || grid[q.z] == '#') {
continue;
}
int cost = dist[v.t][v.p.z] + 1 + (beam[nt][q.z] ? D : 0);
if (dist[nt][q.z] > cost) {
dist[nt][q.z] = cost;
prev[nt][q.z] = d;
queue.add(new S(q, nt, cost));
}
}
int cost = dist[v.t][v.p.z] + 1 + (beam[nt][v.p.z] ? D : 0);
if (dist[nt][v.p.z] > cost) {
dist[nt][v.p.z] = cost;
prev[nt][v.p.z] = 4;
queue.add(new S(v.p, nt, cost));
}
}
throw new RuntimeException();
}
// void calcDist(int s, int t) {
// Deque<Timing> deque = new ArrayDeque<>();
// deque.add(new Timing(ps[s], t));
// int[] dist = new int[N * N];
// int[] prev = new int[N * N];
// Timing[] prevState = new Timing[N * N];
// Arrays.fill(dist, iinf);
// dist[ps[s].z] = 0;
// distances[t][s * (M+3) + s] = 0;
// route[t][s * (M+3) + s] = new int[0];
// while (!deque.isEmpty()) {
// Timing p = deque.removeFirst();
// if (mid[p.p.z] != -1 && mid[p.p.z] != s) {
// distances[t][s * (M+3) + mid[p.p.z]] = dist[p.p.z];
// route[t][s * (M+3) + mid[p.p.z]] = new int[dist[p.p.z]];
// int j = dist[p.p.z];
// Timing cur = p;
// while (j > 0) {
// j--;
// route[t][s * (M+3) + mid[p.p.z]][j] = prev[cur.p.z];
// cur = prevState[cur.p.z];
// }
// }
// int nt = (p.t + 1) % 60;
// for (int d = 0; d < 4; d++) {
// Pos q = p.p.moved(d);
// if (q == null || grid[q.z] == '#' || grid[q.z] == 'E') {
// continue;
// }
// if (beam[q.z][nt]) {
// continue;
// }
// int cost = beam[nt][q.z] ? D : 1;
// if (dist[q.z] > dist[p.p.z] + 1 && q.dist(ps[s]) < iinf) {
// dist[q.z] = dist[p.p.z] + 1;
// prev[q.z] = d;
// prevState[q.z] = p;
// deque.addLast(new Timing(q, nt));
// }
// }
// if (dist[p.p.z] > dist[p.p.z] + 1) {
// dist[p.p.z] = dist[p.p.z] + 1;
// prev[p.p.z] = 5;
// prevState[p.p.z] = p;
// deque.addLast(new Timing(p.p, nt));
// }
// }
// }
void calcDist(int s) {
class S {
private final Pos p;
private final int d;
public S(Pos p, int d) {
this.p = p;
this.d = d;
}
}
PriorityQueue<S> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d));
queue.add(new S(jps[s], 0));
int[] dist = new int[N * N];
Arrays.fill(dist, iinf);
dist[jps[s].z] = 0;
while (!queue.isEmpty()) {
S v = queue.remove();
if (dist[v.p.z] < v.d) {
continue;
}
if (jid[v.p.z] != -1) {
distances[s * (J+3) + jid[v.p.z]] = v.d;
}
for (int d = 0; d < 4; d++) {
Pos q = v.p.moved(d);
if (q == null || grid[q.z] == '#') {
continue;
}
int cost = dist[v.p.z] + avgWait[q.z];
if (dist[q.z] > cost && q.dist(jps[s]) < iinf) {
dist[q.z] = cost;
queue.add(new S(q, cost));
}
}
}
}
void in() {
in.nextInt();
D = in.nextInt();
in.nextInt();
grid = new char[N * N];
int jc = 0;
for (int i = 0; i < N; i++) {
char[] s = in.nextCharArray();
for (int j = 0; j < N; j++) {
grid[i * N + j] = s[j];
if (grid[i * N + j] == 'J') {
jc++;
}
}
}
M = in.nextInt();
J = jc;
jps = new Pos[J + 3];
ps = new Pos[M];
ds = new int[M];
for (int i = 0; i < M; i++) {
int y = in.nextInt();
int x = in.nextInt();
int d = in.nextInt();
ps[i] = pos(x, y);
ds[i] = d;
}
jc = 0;
Arrays.fill(jid, -1);
for (int i = 0; i < N * N; i++) {
if (grid[i] == 'S') {
jps[J] = pos(i);
jid[i] = J;
grid[i] = '.';
} else if (grid[i] == 'K') {
jps[J + 1] = pos(i);
jid[i] = J + 1;
grid[i] = '.';
} else if (grid[i] == 'G') {
jps[J + 2] = pos(i);
jid[i] = J + 2;
grid[i] = '.';
} else if (grid[i] == 'J') {
jid[i] = jc;
jps[jc++] = pos(i);
} else if (grid[i] == 'E') {
grid[i] = '#';
}
}
}
static Pos pos(int x, int y) {
return Pos.instances[y * N + x];
}
static Pos pos(int z) {
return Pos.instances[z];
}
static class Timing {
Pos p;
int t, z;
public Timing(Pos p, int t) {
this.p = p;
this.t = t;
this.z = p.z * 60 + t;
}
}
static class Pos implements Comparable<Pos> {
static Pos[] instances;
static Pos[] moved;
static {
instances = new Pos[N * N];
moved = new Pos[4 * N * N];
for (int i = 0; i < N * N; i++) {
instances[i] = new Pos(i % N, i / N, i);
}
for (int i = 0; i < N * N; i++) {
for (int d = 0; d < 4; d++) { // LURD
int nx = i % N + (d - 1) % 2;
int ny = i / N + (d - 2) % 2;
if (0 <= nx && nx < N && 0 <= ny && ny < N) {
moved[i * 4 + d] = instances[ny * N + nx];
}
}
}
}
final int x, y, z;
private Pos(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
Pos moved(int d) {
return moved[z * 4 + d];
}
int dist(Pos o) {
return Math.abs(x - o.x) + Math.abs(y - o.y);
}
Pos[] neighbors() {
Pos[] p = new Pos[4];
int i = 0;
if ((p[i] = moved(0)) != null) i++;
if ((p[i] = moved(1)) != null) i++;
if ((p[i] = moved(2)) != null) i++;
if ((p[i] = moved(3)) != null) i++;
return i == 4 ? p : Arrays.copyOf(p, i);
}
@Override
public int compareTo(Pos o) {
return Integer.compare(z, o.z);
}
@Override
public boolean equals(Object o) {
return o instanceof Pos && z == ((Pos)o).z;
}
@Override
public int hashCode() {
return z;
}
@Override
public String toString() {
return String.format("(%d, %d)", x, y);
}
}
static void debug(Object... args) {
if (!isLocal) {
return;
}
if (args == null || args.getClass() != Object[].class) {
args = new Object[] {args};
}
System.err.println(Arrays.stream(args).map(obj -> {
Class<?> clazz = obj == null ? null : obj.getClass();
return clazz == byte[].class ? Arrays.toString((byte[])obj) :
clazz == short[].class ? Arrays.toString((short[])obj) :
clazz == int[].class ? Arrays.toString((int[])obj) :
clazz == long[].class ? Arrays.toString((long[])obj) :
clazz == char[].class ? Arrays.toString((char[])obj) :
clazz == float[].class ? Arrays.toString((float[])obj) :
clazz == double[].class ? Arrays.toString((double[])obj) :
clazz == boolean[].class ? Arrays.toString((boolean[])obj) :
obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :
String.valueOf(obj);
}).collect(Collectors.joining(" ")));
}
long elapsed() {
return (long)((System.currentTimeMillis() - startTime) * (isLocal ? 1.7 : 1));
}
boolean elapsed(long timeLimit) {
return elapsed() >= timeLimit;
}
public static void main(String[] args) {
new Main().solve(0);
}
static class Random {
private long x, y, z, w;
Random() {
this(ThreadLocalRandom.current().nextLong());
}
Random(long seed) {
this.x = seed;
for (int i = 0; i < 20; i++) {
rand();
}
}
private long rand() {
long t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ t ^ (t >>> 8);
return x & 0x7fffffff;
}
long next() {
return rand() << 31 | rand();
}
int next(int n) {
return (int)(rand() % n);
}
int next(int l, int r) {
return (int)(rand() % (r - l) + l);
}
double nextDouble() {
return rand() / 2147483647.0;
}
}
static class In {
private final BufferedReader reader;
private StringTokenizer tokenizer;
In(InputStream input) {
this.reader = new BufferedReader(new InputStreamReader(input), 0x10000);
}
String next() {
try {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
} catch (IOException ignored) {
}
return tokenizer.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
char[] nextCharArray() {
return next().toCharArray();
}
String[] nextStringArray(int n) {
String[] s = new String[n];
for (int i = 0; i < n; i++) {
s[i] = next();
}
return s;
}
char[][] nextCharGrid(int n, int m) {
char[][] a = new char[n][m];
for (int i = 0; i < n; i++) {
a[i] = next().toCharArray();
}
return a;
}
int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
int[] nextIntArray(int n, IntUnaryOperator op) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = op.applyAsInt(nextInt());
}
return a;
}
int[][] nextIntMatrix(int h, int w) {
int[][] a = new int[h][w];
for (int i = 0; i < h; i++) {
a[i] = nextIntArray(w);
}
return a;
}
long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = nextLong();
}
return a;
}
long[] nextLongArray(int n, LongUnaryOperator op) {
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = op.applyAsLong(nextLong());
}
return a;
}
long[][] nextLongMatrix(int h, int w) {
long[][] a = new long[h][w];
for (int i = 0; i < h; i++) {
a[i] = nextLongArray(w);
}
return a;
}
List<List<Integer>> nextEdges(int n, int m, boolean directed) {
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
res.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int u = nextInt() - 1;
int v = nextInt() - 1;
res.get(u).add(v);
if (!directed) {
res.get(v).add(u);
}
}
return res;
}
}
}