結果
| 問題 | No.424 立体迷路 |
| ユーザー |
 Kilisame
|
| 提出日時 | 2016-09-26 09:39:36 |
| 言語 | Java (openjdk 23) |
| 結果 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 21 |
ソースコード
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);}}