結果

問題 No.5006 Hidden Maze
ユーザー ks2m
提出日時 2022-06-12 16:29:00
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,584 ms / 2,000 ms
コード長 3,626 bytes
コンパイル時間 2,082 ms
実行使用メモリ 83,136 KB
スコア 85,254
平均クエリ数 148.46
最終ジャッジ日時 2022-06-12 16:30:05
合計ジャッジ時間 49,858 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        int p = Integer.parseInt(sa[2]);
        int h1 = h - 1;
        int w1 = w - 1;
        int q = 100 - p;
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        double[][] tate = new double[h][w];
        double[][] yoko = new double[h][w];
        for (int i = 0; i < h; i++) {
            Arrays.fill(tate[i], 0.15);
            Arrays.fill(yoko[i], 0.15);
        }
        double border = 0.98;
        List<Integer> list = new ArrayList<>(4);
        for (int i = 0; i < 4; i++) {
            list.add(i);
        }
        while (true) {
            border = Math.min(border, 0.995);
            // 探索
            double[][] d = new double[h][w];
            int[][] pre = new int[h][w];
            for (int i = 0; i < h; i++) {
                Arrays.fill(d[i], 1e9);
                Arrays.fill(pre[i], -1);
            }
            d[0][0] = 0;
            Queue<Node> que = new ArrayDeque<>();
            que.add(new Node(0, 0));
            while (!que.isEmpty()) {
                Node cur = que.poll();
                int cx = cur.v / w;
                int cy = cur.v % w;
                Collections.shuffle(list);
                for (int i : list) {
                    int nx = cx + dx[i];
                    int ny = cy + dy[i];
                    if (nx < 0 || h <= nx || ny < 0 || w <= ny) {
                        continue;
                    }
                    double wall = 0;
                    if (i == 0) wall = yoko[cx][cy];
                    else if (i == 1) wall = tate[cx][cy];
                    else if (i == 2) wall = yoko[nx][ny];
                    else if (i == 3) wall = tate[nx][ny];
                    if (wall > border) {
                        continue;
                    }
                    double alt = cur.d + 1 + wall * 2; // TODO 調整
                    if (alt < d[nx][ny]) {
                        que.add(new Node(nx * w + ny, alt));
                        d[nx][ny] = alt;
                        pre[nx][ny] = cur.v;
                    }
                }
            }
            if (pre[h1][w1] == -1) {
                border += 0.002;
                continue;
            }
            // 出力
            StringBuilder sb = new StringBuilder();
            int pos = h1 * w + w1;
            while (pos != 0) {
                int cx = pos / w;
                int cy = pos % w;
                int np = pre[cx][cy];
                int nx = np / w;
                int ny = np % w;
                if (nx < cx) sb.append('D');
                else if (ny < cy) sb.append('R');
                else if (nx > cx) sb.append('U');
                else if (ny > cy) sb.append('L');
                else throw new RuntimeException();
                pos = np;
            }
            sb.reverse();
            System.out.println(sb.toString());
            // 入力
            int a = Integer.parseInt(br.readLine());
            if (a == -1) {
                return;
            }
            // 壁更新
            int cx = 0;
            int cy = 0;
            for (int i = 0; i < a; i++) {
                char c = sb.charAt(i);
                if (c == 'D') {
                    yoko[cx][cy] = 0;
                    cx++;
                } else if (c == 'R') {
                    tate[cx][cy] = 0;
                    cy++;
                } else if (c == 'U') {
                    cx--;
                    yoko[cx][cy] = 0;
                } else if (c == 'L') {
                    cy--;
                    tate[cx][cy] = 0;
                }
            }
            char c = sb.charAt(a);
            if (c == 'D' && yoko[cx][cy] > 0.1) {
                yoko[cx][cy] += (1 - yoko[cx][cy]) * q / 100;
            } else if (c == 'R' && tate[cx][cy] > 0.1) {
                tate[cx][cy] += (1 - tate[cx][cy]) * q / 100;
            } else if (c == 'U' && yoko[cx - 1][cy] > 0.1) {
                yoko[cx - 1][cy] += (1 - yoko[cx - 1][cy]) * q / 100;
            } else if (c == 'L' && tate[cx][cy - 1] > 0.1) {
                tate[cx][cy - 1] += (1 - tate[cx][cy - 1]) * q / 100;
            }
        }
    }
    static class Node implements Comparable<Node> {
        int v;
        double d;
        public Node(int v, double d) {
            this.v = v;
            this.d = d;
        }
        public int compareTo(Node o) {
            return Double.compare(d, o.d);
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0