結果
問題 | No.424 立体迷路 |
ユーザー | Kilisame |
提出日時 | 2016-09-26 09:39:36 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 168 ms / 2,000 ms |
コード長 | 5,048 bytes |
コンパイル時間 | 3,867 ms |
コンパイル使用メモリ | 78,076 KB |
実行使用メモリ | 42,168 KB |
最終ジャッジ日時 | 2024-07-05 07:10:52 |
合計ジャッジ時間 | 7,907 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 128 ms
41,340 KB |
testcase_01 | AC | 128 ms
41,468 KB |
testcase_02 | AC | 131 ms
41,336 KB |
testcase_03 | AC | 130 ms
41,296 KB |
testcase_04 | AC | 130 ms
41,536 KB |
testcase_05 | AC | 128 ms
41,192 KB |
testcase_06 | AC | 126 ms
41,352 KB |
testcase_07 | AC | 130 ms
40,824 KB |
testcase_08 | AC | 111 ms
40,644 KB |
testcase_09 | AC | 130 ms
41,480 KB |
testcase_10 | AC | 119 ms
40,456 KB |
testcase_11 | AC | 112 ms
40,272 KB |
testcase_12 | AC | 113 ms
40,624 KB |
testcase_13 | AC | 127 ms
41,536 KB |
testcase_14 | AC | 128 ms
41,536 KB |
testcase_15 | AC | 129 ms
41,612 KB |
testcase_16 | AC | 127 ms
41,408 KB |
testcase_17 | AC | 159 ms
42,164 KB |
testcase_18 | AC | 161 ms
41,884 KB |
testcase_19 | AC | 158 ms
41,952 KB |
testcase_20 | AC | 159 ms
41,936 KB |
testcase_21 | AC | 127 ms
41,740 KB |
testcase_22 | AC | 129 ms
41,636 KB |
testcase_23 | AC | 127 ms
41,316 KB |
testcase_24 | AC | 165 ms
42,112 KB |
testcase_25 | AC | 168 ms
42,168 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]] && maze[block[0] - 1][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]] && maze[block[0] + 1][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]] && maze[block[0]][block[1] - 1] < 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]] && maze[block[0]][block[1] + 1] < 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); } }