結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2016-09-22 22:37:38 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 1,881 bytes |
コンパイル時間 | 3,368 ms |
コンパイル使用メモリ | 88,012 KB |
実行使用メモリ | 41,964 KB |
最終ジャッジ日時 | 2024-07-05 07:00:42 |
合計ジャッジ時間 | 6,949 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
import java.util.Arrays;import java.util.HashSet;import java.util.LinkedList;import java.util.Scanner;import java.util.Set;public class Main {public static int[][] move_dirs = {{0, 1},{0, -1},{ 1, 0},{-1, 0}};public static boolean in_range(int x, int y, int w, int h){return 0 <= x && x < w && 0 <= y && y < h;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);final int h = sc.nextInt();final int w = sc.nextInt();final int sy = sc.nextInt() - 1;final int sx = sc.nextInt() - 1;final int gy = sc.nextInt() - 1;final int gx = sc.nextInt() - 1;int[][] heights = new int[h][w];for(int i = 0; i < h; i++){final char[] in = sc.next().toCharArray();for(int j = 0; j < w; j++){heights[i][j] = Character.getNumericValue(in[j]);}}boolean[][] visited = new boolean[h][w];LinkedList<Integer> x_queue = new LinkedList<Integer>();LinkedList<Integer> y_queue = new LinkedList<Integer>();x_queue.add(sx); y_queue.add(sy);visited[sy][sx] = true;while(!x_queue.isEmpty()){final int x = x_queue.poll();final int y = y_queue.poll();for(int[] move : move_dirs){final int nx = x + move[0];final int ny = y + move[1];final int nnx = x + move[0] * 2;final int nny = y + move[1] * 2;if(!in_range(nx, ny, w, h)){continue;}if(!visited[ny][nx] && Math.abs(heights[y][x] - heights[ny][nx]) <= 1){visited[ny][nx] = true;x_queue.add(nx); y_queue.add(ny);}if(!in_range(nnx, nny, w, h)){continue;}if(!visited[nny][nnx] && heights[nny][nnx] == heights[y][x] && heights[ny][nx] < heights[y][x]){visited[nny][nnx] = true;x_queue.add(nnx); y_queue.add(nny);}}}System.out.println(visited[gy][gx] ? "YES" : "NO");}}