結果

問題 No.5006 Hidden Maze
ユーザー EvbCFfp1XBEvbCFfp1XB
提出日時 2022-06-12 17:55:17
言語 Java
(openjdk 23)
結果
AC  
実行時間 421 ms / 2,000 ms
コード長 6,695 bytes
コンパイル時間 2,662 ms
実行使用メモリ 72,620 KB
スコア 69,729
平均クエリ数 303.71
最終ジャッジ日時 2022-06-12 17:55:53
合計ジャッジ時間 34,178 ms
ジャッジサーバーID
(参考情報)
judge10 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Scanner;
public class Main {
private static final int[] dr = { -1, 1, 0, 0 };
private static final int[] dc = { 0, 0, -1, 1 };
private static final String dir = "UDLR";
private static final double eps = 1e-9;
private static final int grid_width = 20;
private static final int max_trial = 1001;
private double[][] h = new double[grid_width][grid_width + 1];
private double[][] v = new double[grid_width + 1][grid_width];
private int H;
private int W;
private int p;
public static Random rng = new Random(System.nanoTime());
public static void main(String[] args) {
new Main().run();
}
private void run() {
try (Scanner in = new Scanner(System.in)) {
H = in.nextInt();
W = in.nextInt();
p = in.nextInt();
Utils.debug("H", H, "W", W, "p", p);
for (int r = 0; r < grid_width; r++) {
for (int c = 0; c < grid_width + 1; c++) {
h[r][c] = -1;
}
}
for (int r = 0; r < grid_width + 1; r++) {
for (int c = 0; c < grid_width; c++) {
v[r][c] = -1;
}
}
for (int trial = 1; trial <= max_trial; trial++) {
String path = path();
System.out.println(path);
System.out.flush();
int res = in.nextInt();
if (res == -1) {
Utils.debug("trial", trial, "res", res, "p", p, "length", path.length());
break;
}
update(path, res);
}
} catch (Exception e) {
e.printStackTrace();
}
}
private void update(String path, int length) {
int r = 0;
int c = 0;
for (int i = 0; i < length; i++) {
char ch = path.charAt(i);
int d = direction(ch);
if (d == 0) {
v[r][c] = 0;
} else if (d == 1) {
v[r + 1][c] = 0;
} else if (d == 2) {
h[r][c] = 0;
} else if (d == 3) {
h[r][c + 1] = 0;
}
r += dr[d];
c += dc[d];
}
char ch = path.charAt(length);
int d = direction(ch);
if (d == 0) {
if (v[r][c] < 0) {
v[r][c] = eps;
}
if (v[r][c] > 0.5 * eps) {
v[r][c] += 1e-2 * p;
}
} else if (d == 1) {
if (v[r + 1][c] < 0) {
v[r + 1][c] = eps;
}
if (v[r + 1][c] > 0.5 * eps) {
v[r + 1][c] += 1e-2 * p;
}
} else if (d == 2) {
if (h[r][c] < 0) {
h[r][c] = eps;
}
if (h[r][c] > 0.5 * eps) {
h[r][c] += 1e-2 * p;
}
} else if (d == 3) {
if (h[r][c + 1] < 0) {
h[r][c + 1] = eps;
}
if (h[r][c + 1] > 0.5 * eps) {
h[r][c + 1] += 1e-2 * p;
}
}
}
private String path() {
boolean[][] used = new boolean[grid_width][grid_width];
used[0][0] = true;
PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> {
if (o1.cost < o2.cost) {
return -1;
}
if (o1.cost > o2.cost) {
return 1;
}
if (o1.r + o1.c > o2.r + o2.c) {
return -1;
}
if (o1.r + o1.c < o2.r + o2.c) {
return 1;
}
if (o1.random < o2.random) {
return -1;
}
if (o1.random > o2.random) {
return 1;
}
return 0;
});
q.add(new Node(null, 0, 0, 0, 0));
while (!q.isEmpty()) {
final Node p = q.poll();
int r = p.r;
int c = p.c;
double cost = p.cost;
double random = p.random;
if (r == grid_width - 1 && c == grid_width - 1) {
return reverse(toList(p)).stream().map(node -> "" + dir.charAt(direction(node.parent.r, node.parent.c, node.r, node.c))).reduce("",
                    (sum, s) -> sum + s);
}
for (int d = 0; d < dr.length; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (!Utils.isValid(nr, 0, grid_width) || !Utils.isValid(nc, 0, grid_width)) {
continue;
}
if (!used[nr][nc]) {
used[nr][nc] = true;
q.add(new Node(p, nr, nc, cost + (d <= 1 ? v[r + (d == 1 ? 1 : 0)][c] : h[r][c + (d == 3 ? 1 : 0)]), random + rng.nextDouble()));
}
}
}
throw new AssertionError();
}
private <T> ArrayList<T> reverse(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 node0) {
ArrayList<Node> res = new ArrayList<>();
for (Node current = node0; current.parent != null; current = current.parent) {
res.add(current);
}
return res;
}
private int direction(char c) {
int d = -1;
for (int i = 0; i < 4; i++) {
if (c == dir.charAt(i))
d = i;
}
return d;
}
private int direction(int r1, int c1, int r2, int c2) {
if (r1 > r2) {
return 0;
}
if (r1 < r2) {
return 1;
}
if (c1 > c2) {
return 2;
}
if (c1 < c2) {
return 3;
}
throw new AssertionError();
}
}
final class Utils {
private Utils() {
}
public static final void debug(Object... o) {
System.err.println(toString(o));
}
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 Node {
Node parent;
int r;
int c;
double cost;
double random;
Node(Node parent, int r, int c, double cost, double random) {
this.parent = parent;
this.r = r;
this.c = c;
this.cost = cost;
this.random = random;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0