結果
問題 | No.5006 Hidden Maze |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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;}}