#770471 (Java) No.5006 Hidden Maze

• 問題: No.5006 Hidden Maze
• ユーザー: ks2m
• 提出日時: 2022-06-12 15:04:46
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 431 ms / 2,000 ms
• コード長: 2,488 bytes
• コンパイル時間: 2,206 ms
• 実行使用メモリ: 63,616 KB
• スコア: 1,979
• 平均クエリ数: 981.21
• 最終ジャッジ日時: 2022-06-12 15:05:46
• 合計ジャッジ時間: 36,730 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

ファイルパターン	結果
other	AC * 100

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
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[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        int[][] tate = new int[h][w];
        int[][] yoko = new int[h][w];
        int border = 0;
        while (true) {
            // 探索
            int[][] d = new int[h][w];
            int[][] pre = new int[h][w];
            for (int i = 0; i < h; i++) {
                Arrays.fill(d[i], -1);
                Arrays.fill(pre[i], -1);
            }
            d[0][0] = 0;
            Queue<Integer> que = new ArrayDeque<>();
            que.add(0);
            while (!que.isEmpty()) {
                int cur = que.poll();
                int cx = cur / w;
                int cy = cur % w;
                for (int i = 0; i < 4; i++) {
                    int nx = cx + dx[i];
                    int ny = cy + dy[i];
                    if (nx < 0 || h <= nx || ny < 0 || w <= ny ||
                            i == 0 && yoko[cx][cy] > border ||
                            i == 1 && tate[cx][cy] > border ||
                            i == 2 && yoko[nx][ny] > border ||
                            i == 3 && tate[nx][ny] > border) {
                        continue;
                    }
                    if (d[nx][ny] == -1) {
                        que.add(nx * w + ny);
                        d[nx][ny] = d[cx][cy] + 1;
                        pre[nx][ny] = cur;
                    }
                }
            }
            if (pre[h1][w1] == -1) {
                border++;
                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') cx++;
                else if (c == 'R') cy++;
                else if (c == 'U') cx--;
                else if (c == 'L') cy--;
            }
            char c = sb.charAt(a);
            if (c == 'D') yoko[cx][cy]++;
            else if (c == 'R') tate[cx][cy]++;
            else if (c == 'U') yoko[cx - 1][cy]++;
            else if (c == 'L') tate[cx][cy - 1]++;
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX