結果
問題 | No.5006 Hidden Maze |
ユーザー | ks2m |
提出日時 | 2022-06-12 15:04:46 |
言語 | Java21 (openjdk 21) |
結果 |
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 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 302 ms
60,464 KB |
testcase_01 | AC | 287 ms
60,324 KB |
testcase_02 | AC | 330 ms
59,748 KB |
testcase_03 | AC | 294 ms
59,308 KB |
testcase_04 | AC | 289 ms
59,384 KB |
testcase_05 | AC | 279 ms
58,728 KB |
testcase_06 | AC | 290 ms
59,764 KB |
testcase_07 | AC | 326 ms
59,956 KB |
testcase_08 | AC | 284 ms
58,908 KB |
testcase_09 | AC | 325 ms
59,572 KB |
testcase_10 | AC | 293 ms
59,896 KB |
testcase_11 | AC | 332 ms
59,876 KB |
testcase_12 | AC | 295 ms
58,960 KB |
testcase_13 | AC | 305 ms
59,472 KB |
testcase_14 | AC | 306 ms
59,580 KB |
testcase_15 | AC | 303 ms
59,428 KB |
testcase_16 | AC | 316 ms
59,332 KB |
testcase_17 | AC | 284 ms
58,596 KB |
testcase_18 | AC | 360 ms
59,720 KB |
testcase_19 | AC | 283 ms
58,572 KB |
testcase_20 | AC | 299 ms
58,684 KB |
testcase_21 | AC | 279 ms
58,796 KB |
testcase_22 | AC | 84 ms
49,504 KB |
testcase_23 | AC | 298 ms
59,564 KB |
testcase_24 | AC | 302 ms
59,740 KB |
testcase_25 | AC | 278 ms
58,988 KB |
testcase_26 | AC | 291 ms
58,816 KB |
testcase_27 | AC | 298 ms
59,564 KB |
testcase_28 | AC | 304 ms
59,752 KB |
testcase_29 | AC | 390 ms
59,836 KB |
testcase_30 | AC | 299 ms
59,104 KB |
testcase_31 | AC | 281 ms
58,424 KB |
testcase_32 | AC | 431 ms
61,140 KB |
testcase_33 | AC | 291 ms
59,740 KB |
testcase_34 | AC | 339 ms
59,948 KB |
testcase_35 | AC | 287 ms
59,256 KB |
testcase_36 | AC | 293 ms
60,128 KB |
testcase_37 | AC | 278 ms
59,624 KB |
testcase_38 | AC | 363 ms
59,224 KB |
testcase_39 | AC | 303 ms
58,920 KB |
testcase_40 | AC | 300 ms
59,628 KB |
testcase_41 | AC | 370 ms
59,968 KB |
testcase_42 | AC | 336 ms
59,448 KB |
testcase_43 | AC | 298 ms
60,484 KB |
testcase_44 | AC | 332 ms
58,652 KB |
testcase_45 | AC | 287 ms
59,488 KB |
testcase_46 | AC | 279 ms
59,232 KB |
testcase_47 | AC | 291 ms
59,888 KB |
testcase_48 | AC | 266 ms
59,316 KB |
testcase_49 | AC | 300 ms
59,272 KB |
testcase_50 | AC | 290 ms
59,048 KB |
testcase_51 | AC | 305 ms
59,532 KB |
testcase_52 | AC | 296 ms
59,684 KB |
testcase_53 | AC | 324 ms
60,188 KB |
testcase_54 | AC | 281 ms
59,516 KB |
testcase_55 | AC | 298 ms
59,440 KB |
testcase_56 | AC | 277 ms
58,860 KB |
testcase_57 | AC | 317 ms
59,336 KB |
testcase_58 | AC | 273 ms
59,124 KB |
testcase_59 | AC | 275 ms
59,320 KB |
testcase_60 | AC | 295 ms
58,696 KB |
testcase_61 | AC | 294 ms
59,108 KB |
testcase_62 | AC | 293 ms
58,848 KB |
testcase_63 | AC | 318 ms
59,648 KB |
testcase_64 | AC | 326 ms
59,432 KB |
testcase_65 | AC | 292 ms
59,332 KB |
testcase_66 | AC | 285 ms
58,508 KB |
testcase_67 | AC | 411 ms
63,616 KB |
testcase_68 | AC | 323 ms
58,772 KB |
testcase_69 | AC | 285 ms
59,408 KB |
testcase_70 | AC | 312 ms
59,088 KB |
testcase_71 | AC | 296 ms
59,240 KB |
testcase_72 | AC | 284 ms
59,840 KB |
testcase_73 | AC | 298 ms
59,832 KB |
testcase_74 | AC | 282 ms
59,220 KB |
testcase_75 | AC | 300 ms
59,352 KB |
testcase_76 | AC | 299 ms
59,108 KB |
testcase_77 | AC | 280 ms
58,624 KB |
testcase_78 | AC | 302 ms
58,752 KB |
testcase_79 | AC | 306 ms
59,300 KB |
testcase_80 | AC | 278 ms
58,656 KB |
testcase_81 | AC | 293 ms
60,308 KB |
testcase_82 | AC | 326 ms
59,904 KB |
testcase_83 | AC | 314 ms
59,500 KB |
testcase_84 | AC | 296 ms
58,632 KB |
testcase_85 | AC | 326 ms
59,632 KB |
testcase_86 | AC | 293 ms
59,872 KB |
testcase_87 | AC | 277 ms
59,208 KB |
testcase_88 | AC | 301 ms
59,692 KB |
testcase_89 | AC | 322 ms
59,744 KB |
testcase_90 | AC | 329 ms
59,596 KB |
testcase_91 | AC | 341 ms
59,152 KB |
testcase_92 | AC | 271 ms
58,688 KB |
testcase_93 | AC | 286 ms
58,456 KB |
testcase_94 | AC | 310 ms
59,408 KB |
testcase_95 | AC | 296 ms
59,016 KB |
testcase_96 | AC | 74 ms
48,960 KB |
testcase_97 | AC | 296 ms
59,240 KB |
testcase_98 | AC | 307 ms
60,476 KB |
testcase_99 | AC | 402 ms
61,188 KB |
ソースコード
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]++; } } }