結果
| 問題 | No.5015 Escape from Labyrinth |
| ユーザー |
 EvbCFfp1XB
|
| 提出日時 | 2023-04-16 08:12:01 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 2,914 ms / 3,000 ms |
| コード長 | 30,837 bytes |
| コンパイル時間 | 3,794 ms |
| コンパイル使用メモリ | 90,652 KB |
| 実行使用メモリ | 67,040 KB |
| スコア | 116,550 |
| 最終ジャッジ日時 | 2023-04-16 08:17:03 |
| 合計ジャッジ時間 | 301,346 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,909 ms
65,044 KB |
| testcase_01 | AC | 2,891 ms
65,184 KB |
| testcase_02 | AC | 2,893 ms
65,096 KB |
| testcase_03 | AC | 2,885 ms
64,836 KB |
| testcase_04 | AC | 2,889 ms
65,216 KB |
| testcase_05 | AC | 2,894 ms
65,092 KB |
| testcase_06 | AC | 2,891 ms
65,088 KB |
| testcase_07 | AC | 2,889 ms
65,076 KB |
| testcase_08 | AC | 2,890 ms
64,936 KB |
| testcase_09 | AC | 2,887 ms
64,912 KB |
| testcase_10 | AC | 2,903 ms
65,144 KB |
| testcase_11 | AC | 2,891 ms
65,376 KB |
| testcase_12 | AC | 2,888 ms
64,968 KB |
| testcase_13 | AC | 2,887 ms
64,980 KB |
| testcase_14 | AC | 2,883 ms
65,508 KB |
| testcase_15 | AC | 2,895 ms
65,596 KB |
| testcase_16 | AC | 2,895 ms
65,024 KB |
| testcase_17 | AC | 2,889 ms
65,272 KB |
| testcase_18 | AC | 2,888 ms
64,844 KB |
| testcase_19 | AC | 2,890 ms
65,424 KB |
| testcase_20 | AC | 2,893 ms
65,628 KB |
| testcase_21 | AC | 2,893 ms
65,264 KB |
| testcase_22 | AC | 2,888 ms
65,012 KB |
| testcase_23 | AC | 2,889 ms
64,928 KB |
| testcase_24 | AC | 2,884 ms
65,132 KB |
| testcase_25 | AC | 2,893 ms
64,992 KB |
| testcase_26 | AC | 2,892 ms
67,040 KB |
| testcase_27 | AC | 2,888 ms
64,924 KB |
| testcase_28 | AC | 2,890 ms
65,356 KB |
| testcase_29 | AC | 2,886 ms
64,932 KB |
| testcase_30 | AC | 2,895 ms
65,520 KB |
| testcase_31 | AC | 2,891 ms
64,820 KB |
| testcase_32 | AC | 2,888 ms
65,300 KB |
| testcase_33 | AC | 2,885 ms
64,684 KB |
| testcase_34 | AC | 2,885 ms
65,228 KB |
| testcase_35 | AC | 2,892 ms
65,160 KB |
| testcase_36 | AC | 2,892 ms
64,580 KB |
| testcase_37 | AC | 2,889 ms
65,052 KB |
| testcase_38 | AC | 2,891 ms
65,340 KB |
| testcase_39 | AC | 2,888 ms
64,732 KB |
| testcase_40 | AC | 2,893 ms
64,648 KB |
| testcase_41 | AC | 2,890 ms
62,864 KB |
| testcase_42 | AC | 2,891 ms
65,104 KB |
| testcase_43 | AC | 2,885 ms
64,900 KB |
| testcase_44 | AC | 2,883 ms
64,888 KB |
| testcase_45 | AC | 2,895 ms
64,876 KB |
| testcase_46 | AC | 2,892 ms
65,028 KB |
| testcase_47 | AC | 2,886 ms
64,824 KB |
| testcase_48 | AC | 2,890 ms
65,792 KB |
| testcase_49 | AC | 2,887 ms
65,288 KB |
| testcase_50 | AC | 2,891 ms
65,336 KB |
| testcase_51 | AC | 2,914 ms
65,072 KB |
| testcase_52 | AC | 2,886 ms
64,972 KB |
| testcase_53 | AC | 2,891 ms
64,948 KB |
| testcase_54 | AC | 2,900 ms
63,376 KB |
| testcase_55 | AC | 2,896 ms
62,988 KB |
| testcase_56 | AC | 2,892 ms
65,676 KB |
| testcase_57 | AC | 2,891 ms
64,932 KB |
| testcase_58 | AC | 2,887 ms
65,232 KB |
| testcase_59 | AC | 2,891 ms
65,004 KB |
| testcase_60 | AC | 2,892 ms
65,088 KB |
| testcase_61 | AC | 2,892 ms
64,884 KB |
| testcase_62 | AC | 2,891 ms
65,268 KB |
| testcase_63 | AC | 2,889 ms
65,528 KB |
| testcase_64 | AC | 2,884 ms
65,120 KB |
| testcase_65 | AC | 2,907 ms
65,208 KB |
| testcase_66 | AC | 2,892 ms
66,924 KB |
| testcase_67 | AC | 2,890 ms
64,904 KB |
| testcase_68 | AC | 2,882 ms
65,368 KB |
| testcase_69 | AC | 2,890 ms
65,616 KB |
| testcase_70 | AC | 2,895 ms
65,160 KB |
| testcase_71 | AC | 2,891 ms
65,256 KB |
| testcase_72 | AC | 2,891 ms
65,008 KB |
| testcase_73 | AC | 2,890 ms
65,248 KB |
| testcase_74 | AC | 2,892 ms
64,800 KB |
| testcase_75 | AC | 2,893 ms
65,100 KB |
| testcase_76 | AC | 2,891 ms
65,132 KB |
| testcase_77 | AC | 2,891 ms
65,012 KB |
| testcase_78 | AC | 2,890 ms
64,888 KB |
| testcase_79 | AC | 2,886 ms
63,536 KB |
| testcase_80 | AC | 2,893 ms
65,020 KB |
| testcase_81 | AC | 2,893 ms
65,060 KB |
| testcase_82 | AC | 2,892 ms
65,188 KB |
| testcase_83 | AC | 2,888 ms
63,180 KB |
| testcase_84 | AC | 2,887 ms
65,268 KB |
| testcase_85 | AC | 2,892 ms
65,508 KB |
| testcase_86 | AC | 2,911 ms
65,036 KB |
| testcase_87 | AC | 2,890 ms
64,836 KB |
| testcase_88 | AC | 2,910 ms
65,560 KB |
| testcase_89 | AC | 2,889 ms
65,444 KB |
| testcase_90 | AC | 2,893 ms
65,844 KB |
| testcase_91 | AC | 2,888 ms
65,740 KB |
| testcase_92 | AC | 2,890 ms
64,924 KB |
| testcase_93 | AC | 2,889 ms
65,280 KB |
| testcase_94 | AC | 2,889 ms
67,000 KB |
| testcase_95 | AC | 2,894 ms
65,504 KB |
| testcase_96 | AC | 2,890 ms
65,016 KB |
| testcase_97 | AC | 2,893 ms
65,100 KB |
| testcase_98 | AC | 2,889 ms
65,456 KB |
| testcase_99 | AC | 2,899 ms
65,092 KB |
ソースコード
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
private static final int grid_size = 60;
private static final int max_hp = 1500;
private static final int[] dy = { -1, 1, 0, 0 };
private static final int[] dx = { 0, 0, -1, 1 };
private static final char[] dir = "UDLR".toCharArray();
private static final int inf = (int) 1e9;
private static final int[] dr = { -1, 0, 0, 1, };
private static final int[] dc = { 0, -1, 1, 0, };
private static final int EMPTY = 0;
private static final int WALL = 1;
private static final int JEWEL = 2;
private static final int GUNPOWDER = 3;
private static final int DETECTOR = 4;
private static final int BLOCK = 5;
private int N;
private int D;
private int H;
private int[][] map;
private int sr;
private int sc;
private int gr;
private int gc;
private int kr;
private int kc;
private int sumDistance;
private ArrayList<Point> points = new ArrayList<>();
private int bestSumDistance;
private ArrayList<Point> bestPoints = new ArrayList<>();
private ArrayList<Point> removedPoints = new ArrayList<>();
private int thresholdDistance;
private int M;
private int[][] detectTurns0;
public static Watch watch = new Watch();
public static PCG_XSH_RR rng = new PCG_XSH_RR(System.nanoTime());
public static SAState sa = new SAState();
private ArrayList<Integer>[][] detectTurns;
private int[][] enemy_num;
private ArrayList<Enemy> E;
private int score;
private ArrayList<Move> solution;
private int bestScore;
private ArrayList<Move> bestSolution;
public static void main(String[] args) throws Exception {
new Main().run();
}
private void run() {
read();
solve();
write();
}
private void write() {
for (Move move : solution) {
System.out.println(move);
}
System.out.flush();
}
private void solve() {
detectTurns = new ArrayList[N][N];
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
detectTurns[r][c] = new ArrayList<>();
}
}
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (map[r][c] == DETECTOR) {
for (int d = 0; d < dr.length; d++) {
for (int length = 1; length < N; length++) {
int nr = r + length * dr[d];
int nc = c + length * dc[d];
if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
break;
}
if (map[nr][nc] == WALL) {
break;
}
if (map[nr][nc] == DETECTOR) {
break;
}
if (map[nr][nc] == BLOCK) {
break;
}
detectTurns[nr][nc].add(detectTurns0[r][c]);
}
}
}
}
}
points.add(new Point(sr, sc));
points.addAll(bfs2(sr, sc));
points.add(new Point(gr, gc));
points.add(points.size() / 2, new Point(kr, kc));
sumDistance = calculataSumDistance();
score = (int) -1e9;
solution = new ArrayList<>();
bestScore = (int) -1e9;
bestSolution = new ArrayList<>();
multiSA();
Utils.debug("solve", "time", watch.getSecondString());
}
private int calculataSumDistance() {
int sumDistance = 0;
for (int i = 1; i < points.size(); i++) {
sumDistance += manhattanDistance(points.get(i - 1), points.get(i));
}
return sumDistance;
}
private void multiSA() {
int numRestart = 20;
double startTime = watch.getSecond();
double endTime = 2.75;
double remainTime = endTime - startTime;
double startStartTemperature = 1e1;
double endStartTemperature = 1e-9;
int ok = 0;
int ng = 1000;
for (double restart = 0; restart < numRestart; restart++) {
if (restart % 5 == 0) {
ok = 0;
ng = 1000;
}
thresholdDistance = (ok + ng) / 2;
sa.startTime = startTime + remainTime * restart / numRestart;
sa.endTime = -0.05 + startTime + remainTime * (restart + 1) / numRestart;
sa.startTemperature = endStartTemperature + (startStartTemperature - endStartTemperature) * ((numRestart - restart) / numRestart);
sa.endTemperature = 1e-9;
SA();
solution.clear();
for (int j = 1; j < points.size(); j++) {
ArrayList<Node> moves = bfs(points.get(j - 1).r, points.get(j - 1).c, solution.size(), points.get(j).r, points.get(j).c);
for (int i = 1; i < moves.size(); i++) {
solution.add(new Move('M', direction(moves.get(i - 1).r, moves.get(i - 1).c, moves.get(i).r, moves.get(i).c)));
}
}
score = simulate(solution);
if (score <= 1) {
ng = thresholdDistance;
} else {
ok = thresholdDistance;
}
saveBest();
}
loadBest();
Utils.debug("multiSA", sumDistance, "time", watch.getSecondString());
}
private void saveBest() {
if (score > bestScore) {
bestScore = score;
bestSolution.clear();
for (int i = 0; i < solution.size(); i++) {
bestSolution.add(solution.get(i));
}
}
}
private void loadBest() {
score = bestScore;
solution.clear();
for (int i = 0; i < bestSolution.size(); i++) {
solution.add(bestSolution.get(i));
}
}
private void SA() {
sa.init();
++sa.numIterations;
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 5) - 1)) == 0) {
sa.update();
if (sa.isTLE()) {
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%5d", points.size()), String.format("%5d", sumDistance), String.format("%5d", score), String.format("%5d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), "time", watch.getSecondString());
break;
}
}
mutate();
}
}
private void mutate() {
double random = 3 * rng.nextDouble();
if (random < 1) {
remove();
} else if (random < 2) {
add();
} else if (random < 3) {
reverse();
} else if (random < 4) {
swap();
} else if (random < 5) {
insert();
}
}
private void remove() {
if (sumDistance < thresholdDistance) {
return;
}
int index1 = 1 + (int) ((points.size() - 2) * rng.nextDouble());
final Point p = points.get(index1);
if (p.r == sr && p.c == sc) {
return;
}
if (p.r == kr && p.c == kc) {
return;
}
if (p.r == gr && p.c == gc) {
return;
}
final int before = manhattanDistance(points.get(index1 - 1), p) + manhattanDistance(p, points.get(index1 + 1));
final int after = manhattanDistance(points.get(index1 - 1), points.get(index1 + 1));
final int deltaScore = after - before;
if (sa.acceptS(deltaScore)) {
sumDistance += deltaScore;
points.remove(index1);
removedPoints.add(p);
} else {
}
}
private void add() {
if (removedPoints.size() == 0) {
return;
}
if (sumDistance > thresholdDistance) {
return;
}
int index1 = (int) (removedPoints.size() * rng.nextDouble());
final Point p = removedPoints.get(index1);
int index2 = 1 + (int) ((points.size() - 2) * rng.nextDouble());
final int before = manhattanDistance(points.get(index2 - 1), points.get(index2));
final int after = manhattanDistance(points.get(index2 - 1), p) + manhattanDistance(p, points.get(index2));
final int deltaScore = after - before;
if (sa.acceptS(deltaScore)) {
sumDistance += deltaScore;
points.add(index2, p);
removedPoints.remove(index1);
} else {
}
}
private void swap() {
if (points.size() <= 3) {
return;
}
int index1 = 1 + (int) ((points.size() - 2) * rng.nextDouble());
int index2 = 1 + (int) ((points.size() - 2 - 1) * rng.nextDouble());
if (index2 >= index1) {
index2++;
}
if (index1 > index2) {
int swap = index1;
index1 = index2;
index2 = swap;
}
if (index1 + 1 == index2) {
final Point p1 = points.get(index1 - 1);
final Point p2 = points.get(index1);
final Point p5 = points.get(index2);
final Point p6 = points.get(index2 + 1);
final int before = manhattanDistance(p1, p2) + manhattanDistance(p5, p6);
final int after = manhattanDistance(p1, p5) + manhattanDistance(p2, p6);
final int deltaScore = after - before;
if (sa.acceptS(deltaScore)) {
sumDistance += deltaScore;
Collections.swap(points, index1, index2);
} else {
}
} else {
final Point p1 = points.get(index1 - 1);
final Point p2 = points.get(index1);
final Point p3 = points.get(index1 + 1);
final Point p4 = points.get(index2 - 1);
final Point p5 = points.get(index2);
final Point p6 = points.get(index2 + 1);
final int before = manhattanDistance(p1, p2) + manhattanDistance(p2, p3);
final int before2 = manhattanDistance(p4, p5) + manhattanDistance(p5, p6);
final int after = manhattanDistance(p1, p5) + manhattanDistance(p5, p3);
final int after2 = manhattanDistance(p4, p2) + manhattanDistance(p2, p6);
final int deltaScore = after - before + after2 - before2;
if (sa.acceptS(deltaScore)) {
sumDistance += deltaScore;
Collections.swap(points, index1, index2);
} else {
}
}
}
private void reverse() {
if (points.size() <= 3) {
return;
}
int index1 = 1 + (int) ((points.size() - 2) * rng.nextDouble());
int index2 = 1 + (int) ((points.size() - 2 - 1) * rng.nextDouble());
if (index2 >= index1) {
index2++;
}
if (index1 > index2) {
int swap = index1;
index1 = index2;
index2 = swap;
}
final Point p1 = points.get(index1 - 1);
final Point p2 = points.get(index1);
final Point p5 = points.get(index2);
final Point p6 = points.get(index2 + 1);
final int before = manhattanDistance(p1, p2) + manhattanDistance(p5, p6);
final int after = manhattanDistance(p1, p5) + manhattanDistance(p2, p6);
final int deltaScore = after - before;
if (sa.acceptS(deltaScore)) {
sumDistance += deltaScore;
for (int l = index1, r = index2; l < r; l++, r--) {
Collections.swap(points, l, r);
}
} else {
}
}
private void insert() {
if (points.size() <= 3) {
return;
}
int index1 = 1 + (int) ((points.size() - 2) * rng.nextDouble());
final Point p1 = points.get(index1 - 1);
final Point p2 = points.get(index1);
final Point p3 = points.get(index1 + 1);
final int before = manhattanDistance(p1, p2) + manhattanDistance(p2, p3);
final int after = manhattanDistance(p1, p3);
points.remove(index1);
int index2 = 1 + (int) ((points.size() - 2 - 0) * rng.nextDouble());
final Point p4 = points.get(index2 - 1);
final Point p5 = points.get(index2);
final int before2 = manhattanDistance(p4, p5);
final int after2 = manhattanDistance(p4, p2) + manhattanDistance(p2, p5);
final int deltaScore = after - before + after2 - before2;
if (sa.acceptS(deltaScore)) {
sumDistance += deltaScore;
points.add(index2, p2);
} else {
points.add(index1, p2);
}
}
private char direction(int r, int c, int r2, int c2) {
if (r2 - r < 0) {
return dir[0];
}
if (r2 - r > 0) {
return dir[1];
}
if (c2 - c < 0) {
return dir[2];
}
if (c2 - c > 0) {
return dir[3];
}
throw new AssertionError();
}
private ArrayList<Node> bfs(int sr, int sc, int turn, int gr, int gc) {
boolean[][] used = new boolean[N][N];
PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.damage, o2.damage));
{
used[sr][sc] = true;
queue.add(new Node(null, sr, sc, turn, 0));
}
for (; !queue.isEmpty();) {
Node node = queue.poll();
if (node.r == gr && node.c == gc) {
return reverse2(toList(node));
}
for (int d = 0; d < dr.length; d++) {
int nr = node.r + dr[d];
int nc = node.c + dc[d];
if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
continue;
}
if (map[nr][nc] == WALL) {
continue;
}
if (map[nr][nc] == BLOCK) {
continue;
}
if (map[nr][nc] == DETECTOR) {
continue;
}
if (used[nr][nc]) {
continue;
}
used[nr][nc] = true;
int ndamage = node.damage + 1;
for (Integer turn2 : detectTurns[nr][nc]) {
if ((node.turn + 1) % turn2 == 0) {
ndamage += D;
}
}
queue.add(new Node(node, nr, nc, node.turn + 1, ndamage));
}
}
throw new AssertionError();
}
private ArrayList<Point> bfs2(int sr, int sc) {
ArrayList<Point> jewels = new ArrayList<>();
boolean[][] used = new boolean[N][N];
LinkedList<Node> queue = new LinkedList<>();
{
used[sr][sc] = true;
queue.add(new Node(null, sr, sc));
}
for (; !queue.isEmpty();) {
Node node = queue.poll();
if (map[node.r][node.c] == JEWEL) {
jewels.add(new Point(node.r, node.c));
}
for (int d = 0; d < dr.length; d++) {
int nr = node.r + dr[d];
int nc = node.c + dc[d];
if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
continue;
}
if (map[nr][nc] == WALL) {
continue;
}
if (map[nr][nc] == BLOCK) {
continue;
}
if (map[nr][nc] == DETECTOR) {
continue;
}
if (used[nr][nc]) {
continue;
}
used[nr][nc] = true;
queue.add(new Node(node, nr, nc));
}
}
return jewels;
}
private void read() {
try (Scanner in = new Scanner(System.in)) {
N = in.nextInt();
watch.init();
D = in.nextInt();
Utils.debug("D", D);
H = in.nextInt();
map = new int[N][N];
int M2 = 0;
for (int r = 0; r < N; r++) {
String line = in.next();
for (int c = 0; c < N; c++) {
if (line.charAt(c) == '.') {
map[r][c] = EMPTY;
} else if (line.charAt(c) == '#') {
map[r][c] = WALL;
} else if (line.charAt(c) == 'S') {
sr = r;
sc = c;
} else if (line.charAt(c) == 'G') {
gr = r;
gc = c;
} else if (line.charAt(c) == 'K') {
kr = r;
kc = c;
} else if (line.charAt(c) == 'J') {
map[r][c] = JEWEL;
} else if (line.charAt(c) == 'F') {
map[r][c] = GUNPOWDER;
} else if (line.charAt(c) == 'E') {
map[r][c] = DETECTOR;
M2++;
}
}
}
M = in.nextInt();
detectTurns0 = new int[N][N];
enemy_num = new int[N][N];
E = new ArrayList<>();
for (int i = 0; i < M; i++) {
int y = in.nextInt();
int x = in.nextInt();
int d = in.nextInt();
detectTurns0[y][x] = d;
enemy_num[y][x] = i;
E.add(new Enemy(y, x, d));
}
} catch (Exception e) {
e.printStackTrace();
}
}
private <T> ArrayList<T> reverse2(ArrayList<T> list) {
for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
list.set(r, list.set(l, list.get(r)));
}
return list;
}
private ArrayList<Node> toList(Node state0) {
ArrayList<Node> res = new ArrayList<>();
for (Node current = state0; current != null; current = current.parent) {
res.add(current);
}
return res;
}
private ArrayList<Node> toList0(Node state0) {
ArrayList<Node> res = new ArrayList<>();
for (Node current = state0; current.parent != null; current = current.parent) {
res.add(current);
}
return res;
}
private static int manhattanDistance(Point p, Point q) {
return manhattanDistance(p.r, p.c, q.r, q.c);
}
private static int manhattanDistance(int r, int c, int r2, int c2) {
return Math.abs(r - r2) + Math.abs(c - c2);
}
private int direction(char c) {
int d = -1;
for (int i = 0; i < 4; i++) {
if (c == dir[i])
d = i;
}
return d;
}
private boolean range_out(int y, int x) {
if (y < 0 || y >= grid_size)
return true;
if (x < 0 || x >= grid_size)
return true;
return false;
}
private int simulate(ArrayList<Move> solution) {
int now_y = sr;
int now_x = sc;
boolean get_key = false;
int fire_left = 0;
int damage = 0;
int score = 0;
int jewel_value = 10;
int turn = 0;
int[][] map = new int[N][N];
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
map[r][c] = this.map[r][c];
}
}
for (int i = 0; i < solution.size(); i++) {
char c = solution.get(i).a;
if (c == 'S') {
} else {
char d = solution.get(i).b;
int dir = direction(d);
if (dir == -1) {
System.err.println("invalid output");
return 1;
}
if (c == 'M') {
now_y += dy[dir];
now_x += dx[dir];
if (range_out(now_y, now_x)) {
System.err.println("invalid move : range out");
return 1;
}
int cell = map[now_y][now_x];
if (cell == WALL) {
System.err.println("invalid move : wall");
return 1;
} else if (cell == BLOCK) {
System.err.println("invalid move : block");
return 1;
} else if (cell == DETECTOR) {
System.err.println("invalid move : enemy");
return 1;
} else if (now_y == kr && now_x == kc) {
get_key = true;
map[now_y][now_x] = EMPTY;
} else if (cell == GUNPOWDER) {
fire_left++;
map[now_y][now_x] = EMPTY;
} else if (cell == JEWEL) {
score += jewel_value;
map[now_y][now_x] = EMPTY;
} else if (now_y == gr && now_x == gc) {
if (get_key) {
return score;
}
}
} else if (c == 'B') {
int ny = now_y + dy[dir];
int nx = now_x + dx[dir];
if (range_out(ny, nx)) {
System.err.println("failed to create a block : range out");
return 1;
}
if (map[ny][nx] != EMPTY && map[ny][nx] != BLOCK) {
System.err.println("failed to create a block : not empty");
return 1;
}
if (map[ny][nx] == EMPTY) {
map[ny][nx] = BLOCK;
} else {
map[ny][nx] = EMPTY;
}
} else if (c == 'F') {
if (fire_left <= 0) {
System.err.println("failed to use the magic : no fire");
return 1;
}
fire_left--;
int ny = now_y + dy[dir];
int nx = now_x + dx[dir];
while (!range_out(ny, nx)) {
if (map[ny][nx] == WALL || map[ny][nx] == BLOCK) {
break;
} else if (map[ny][nx] == DETECTOR) {
map[ny][nx] = EMPTY;
int num = enemy_num[ny][nx];
E.get(num).destroyed = true;
break;
}
ny += dy[dir];
nx += dx[dir];
}
} else {
System.err.println("invalid output");
return 1;
}
}
for (int k = 0; k < 4; k++) {
int ny = now_y + dy[k];
int nx = now_x + dx[k];
while (!range_out(ny, nx)) {
int cell = map[ny][nx];
if (cell == WALL || cell == BLOCK) {
break;
} else if (cell == DETECTOR) {
int num = enemy_num[ny][nx];
int d2 = E.get(num).d;
if (turn % d2 == 0) {
damage += D;
}
break;
}
ny += dy[k];
nx += dx[k];
}
}
damage++;
if (damage >= H) {
Utils.debug("turn", turn, "damage", damage);
System.err.println("failed to escape from the labyrinth");
return 1;
}
turn++;
}
return 1;
}
}
class Point {
int r;
int c;
Point(int r, int c) {
this.r = r;
this.c = c;
}
}
class SAState {
public boolean useTime = true;
public double startTime;
public double endTime;
public double time;
public double startTemperature;
public double endTemperature;
public double inverseTemperature;
public double lastAcceptTemperature;
public double startRange;
public double endRange;
public double range;
public int numIterations;
public int validIterations;
public int acceptIterations;
private double[] log = new double[32768];
public SAState() {
for (int i = 0; i < log.length; i++) {
log[i] = Math.log((i + 0.5) / log.length);
}
}
public void init() {
numIterations = 0;
validIterations = 0;
acceptIterations = 0;
startTime = useTime ? Main.watch.getSecond() : numIterations;
update();
lastAcceptTemperature = inverseTemperature;
}
public void update() {
updateTime();
updateTemperature();
updateRange();
}
public boolean useExp = !true;
public void updateTemperature() {
if (useExp) {
double time0to1 = elapsedPercentage(startTime, endTime, time);
double startY = startTemperature;
double endY = endTemperature;
double startX = Math.log(startY);
double endX = Math.log(endY);
double xStartToEnd = interpolate(startX, endX, time0to1);
double temperature = Math.exp(xStartToEnd);
inverseTemperature = 1.0 / temperature;
} else {
double time0to1 = elapsedPercentage(startTime, endTime, time);
double startY = startTemperature;
double endY = endTemperature;
double temperature = interpolate(startY, endY, time0to1);
inverseTemperature = 1.0 / temperature;
}
}
private double elapsedPercentage(double min, double max, double v) {
return (v - min) / (max - min);
}
private double interpolate(double v0, double v1, double d0to1) {
return v0 + (v1 - v0) * d0to1;
}
public void updateRange() {
range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}
public void updateTime() {
time = useTime ? Main.watch.getSecond() : numIterations;
}
public boolean isTLE() {
return time >= endTime;
}
public boolean accept(double deltaScore) {
return acceptB(deltaScore);
}
public boolean acceptB(double deltaScore) {
validIterations++;
if (deltaScore > -1e-9) {
acceptIterations++;
return true;
}
double d = deltaScore * inverseTemperature;
if (d < -10) {
return false;
}
if (log[Main.rng.nextInt() & 32767] < d) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}
public boolean acceptS(double deltaScore) {
validIterations++;
if (deltaScore < 1e-9) {
acceptIterations++;
return true;
}
double d = -deltaScore * inverseTemperature;
if (d < -10) {
return false;
}
if (log[Main.rng.nextInt() & 32767] < d) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}
}
final class Utils {
private Utils() {
}
public static final void debug(Object... o) {
System.err.println(toString(o));
System.err.flush();
}
public static final String toString(Object... o) {
return Arrays.deepToString(o);
}
public static boolean isValid(int v, int min, int minUpper) {
return v >= min && v < minUpper;
}
}
class Watch {
private long start;
public Watch() {
init();
}
public double getSecond() {
return (System.nanoTime() - start) * 1e-9;
}
public void init() {
init(System.nanoTime());
}
private void init(long start) {
this.start = start;
}
public String getSecondString() {
return toString(getSecond());
}
public static final String toString(double second) {
if (second < 60) {
return String.format("%5.2fs", second);
} else if (second < 60 * 60) {
int minute = (int) (second / 60);
return String.format("%2dm%2ds", minute, (int) (second % 60));
} else {
int hour = (int) (second / (60 * 60));
int minute = (int) (second / 60);
return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
}
}
}
final class PCG_XSH_RR {
private long state = 5342;
public PCG_XSH_RR(final long state) {
this.state = state;
}
public int nextInt() {
final long oldstate = state;
state = oldstate * 6364136223846793005L + 521L;
final int xorshift = (int) (((oldstate >>> 18) ^ oldstate) >>> 27);
final int rotation = (int) (oldstate >>> 59);
return (xorshift >>> rotation) | (xorshift << (-rotation & 31));
}
public int nextInt(int n) {
return (int) (n * nextDouble());
}
public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}
}
class Node {
Node parent;
int r;
int c;
int turn;
int damage;
Node(Node parent, int r, int c) {
this.parent = parent;
this.r = r;
this.c = c;
}
Node(Node parent, int r, int c, int turn, int damage) {
this.parent = parent;
this.r = r;
this.c = c;
this.turn = turn;
this.damage = damage;
}
}
class Move {
char a;
char b;
Move(char a, char b) {
this.a = a;
this.b = b;
}
@Override
public String toString() {
return a + " " + b;
}
}
class Enemy {
public boolean destroyed;
int y, x, d;
Enemy(int y, int x, int d) {
this.y = y;
this.x = x;
this.d = d;
this.destroyed = false;
}
}