結果
問題 | No.424 立体迷路 |
ユーザー | Kilisame |
提出日時 | 2016-09-26 09:37:07 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,812 bytes |
コンパイル時間 | 3,408 ms |
コンパイル使用メモリ | 78,424 KB |
実行使用メモリ | 43,384 KB |
最終ジャッジ日時 | 2024-04-29 12:00:48 |
合計ジャッジ時間 | 7,819 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 108 ms
40,364 KB |
testcase_01 | AC | 111 ms
40,912 KB |
testcase_02 | AC | 109 ms
40,624 KB |
testcase_03 | AC | 119 ms
41,572 KB |
testcase_04 | AC | 125 ms
41,632 KB |
testcase_05 | AC | 116 ms
41,120 KB |
testcase_06 | AC | 108 ms
40,360 KB |
testcase_07 | AC | 111 ms
40,820 KB |
testcase_08 | AC | 118 ms
41,340 KB |
testcase_09 | AC | 107 ms
40,912 KB |
testcase_10 | AC | 121 ms
41,360 KB |
testcase_11 | AC | 110 ms
40,596 KB |
testcase_12 | AC | 113 ms
40,624 KB |
testcase_13 | AC | 127 ms
42,100 KB |
testcase_14 | AC | 121 ms
41,492 KB |
testcase_15 | AC | 128 ms
41,956 KB |
testcase_16 | AC | 125 ms
41,400 KB |
testcase_17 | AC | 154 ms
41,920 KB |
testcase_18 | AC | 163 ms
42,284 KB |
testcase_19 | AC | 174 ms
42,644 KB |
testcase_20 | AC | 176 ms
42,796 KB |
testcase_21 | AC | 122 ms
41,436 KB |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | AC | 162 ms
42,396 KB |
testcase_25 | AC | 162 ms
43,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); } }