結果
問題 | No.424 立体迷路 |
ユーザー | Kilisame |
提出日時 | 2016-09-26 09:37:07 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,812 bytes |
コンパイル時間 | 4,322 ms |
コンパイル使用メモリ | 77,980 KB |
実行使用メモリ | 56,712 KB |
最終ジャッジ日時 | 2024-11-18 15:05:16 |
合計ジャッジ時間 | 8,754 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 122 ms
54,292 KB |
testcase_01 | AC | 130 ms
53,920 KB |
testcase_02 | AC | 114 ms
53,068 KB |
testcase_03 | AC | 133 ms
54,132 KB |
testcase_04 | AC | 134 ms
54,236 KB |
testcase_05 | AC | 129 ms
54,352 KB |
testcase_06 | AC | 129 ms
54,308 KB |
testcase_07 | AC | 126 ms
53,900 KB |
testcase_08 | AC | 128 ms
54,036 KB |
testcase_09 | AC | 123 ms
54,024 KB |
testcase_10 | AC | 124 ms
54,124 KB |
testcase_11 | AC | 134 ms
54,052 KB |
testcase_12 | AC | 132 ms
54,132 KB |
testcase_13 | AC | 133 ms
54,200 KB |
testcase_14 | AC | 128 ms
54,040 KB |
testcase_15 | AC | 133 ms
54,368 KB |
testcase_16 | AC | 125 ms
54,208 KB |
testcase_17 | AC | 164 ms
54,728 KB |
testcase_18 | AC | 163 ms
54,612 KB |
testcase_19 | AC | 166 ms
54,432 KB |
testcase_20 | AC | 159 ms
54,384 KB |
testcase_21 | AC | 118 ms
52,836 KB |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | AC | 163 ms
54,500 KB |
testcase_25 | AC | 168 ms
54,384 KB |
ソースコード
package puzzle.yukicoder.threedimensionalmaze; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class ThreeDimensionalMaze { private static int[][] maze; private static boolean[][] reached; /* シンプルにルールに基づき、スタートから移動可能な場所をチェックしつつ幅優先探索する */ public static void main(String[] args) { Scanner cin = new Scanner(System.in); int h = Integer.parseInt(cin.next()); int w = Integer.parseInt(cin.next()); int[] start = new int[2]; start[0] = Integer.parseInt(cin.next()) - 1; start[1] = Integer.parseInt(cin.next()) - 1; int[] goal = new int[2]; goal[0] = Integer.parseInt(cin.next()) - 1; goal[1] = Integer.parseInt(cin.next()) - 1; maze = new int[h][w]; reached = new boolean[h][w]; for (int i = 0; i < h; i++) { String[] lines = cin.next().split(""); for (int j = 0; j < w; j++) { maze[i][j] = Integer.parseInt(lines[j]); } } cin.close(); List<int[]> currentBlocks = new ArrayList<int[]>(); List<int[]> nextBlocks = new ArrayList<int[]>(); currentBlocks.add(start); reached[start[0]][start[1]] = true; while (!currentBlocks.isEmpty()) { for (int[] block : currentBlocks) { /* 上1ブロック */ if (block[0] > 0 && !reached[block[0] - 1][block[1]] && (maze[block[0] - 1][block[1]] >= maze[block[0]][block[1]] - 1 && maze[block[0] - 1][block[1]] <= maze[block[0]][block[1]] + 1)) { nextBlocks.add(new int[] {block[0] - 1, block[1]}); reached[block[0] - 1][block[1]] = true; } /* 上2ブロック */ if (block[0] > 1 && !reached[block[0] - 2][block[1]] && maze[block[0] - 2][block[1]] == maze[block[0]][block[1]]) { nextBlocks.add(new int[] {block[0] - 2, block[1]}); reached[block[0] - 2][block[1]] = true; } /* 下1ブロック */ if (block[0] < h - 1 && !reached[block[0] + 1][block[1]] && (maze[block[0] + 1][block[1]] >= maze[block[0]][block[1]] - 1 && maze[block[0] + 1][block[1]] <= maze[block[0]][block[1]] + 1)) { nextBlocks.add(new int[] {block[0] + 1, block[1]}); reached[block[0] + 1][block[1]] = true; } /* 下2ブロック */ if (block[0] < h - 2 && !reached[block[0] + 2][block[1]] && maze[block[0] + 2][block[1]] == maze[block[0]][block[1]]) { nextBlocks.add(new int[] {block[0] + 2, block[1]}); reached[block[0] + 2][block[1]] = true; } /* 右1ブロック */ if (block[1] > 0 && !reached[block[0]][block[1] - 1] && (maze[block[0]][block[1] - 1] >= maze[block[0]][block[1]] - 1 && maze[block[0]][block[1] - 1] <= maze[block[0]][block[1]] + 1)) { nextBlocks.add(new int[] {block[0], block[1] - 1}); reached[block[0]][block[1] - 1] = true; } /* 右2ブロック */ if (block[1] > 1 && !reached[block[0]][block[1] - 2] && maze[block[0]][block[1] - 2] == maze[block[0]][block[1]]) { nextBlocks.add(new int[] {block[0], block[1] - 2}); reached[block[0]][block[1] - 2] = true; } /* 左1ブロック */ if (block[1] < w - 1 && !reached[block[0]][block[1] + 1] && (maze[block[0]][block[1] + 1] >= maze[block[0]][block[1]] - 1 && maze[block[0]][block[1] + 1] <= maze[block[0]][block[1]] + 1)) { nextBlocks.add(new int[] {block[0], block[1] + 1}); reached[block[0]][block[1] + 1] = true; } /* 左2ブロック */ if (block[1] < w - 2 && !reached[block[0]][block[1] + 2] && maze[block[0]][block[1] + 2] == maze[block[0]][block[1]]) { nextBlocks.add(new int[] {block[0], block[1] + 2}); reached[block[0]][block[1] + 2] = true; } } if (reached[goal[0]][goal[1]]) { exit(true); } currentBlocks = nextBlocks; nextBlocks = new ArrayList<int[]>(); } exit(false); } private static void exit(boolean result) { if (result) { System.out.println("YES"); } else { System.out.println("NO"); } System.exit(0); } }