結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2016-09-22 22:38:29 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 112 ms / 2,000 ms |
コード長 | 1,545 bytes |
コンパイル時間 | 2,209 ms |
コンパイル使用メモリ | 79,448 KB |
実行使用メモリ | 41,560 KB |
最終ジャッジ日時 | 2024-07-05 07:00:50 |
合計ジャッジ時間 | 5,456 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
import java.util.ArrayList;import java.util.Scanner;public class Main {static Scanner sc = new Scanner(System.in);static int[] DX = { 1, 0, -1, 0 };static int[] DY = { 0, 1, 0, -1 };public static void main(String[] args) {int H = sc.nextInt();int W = sc.nextInt();int SX = sc.nextInt() - 1;int SY = sc.nextInt() - 1;int GX = sc.nextInt() - 1;int GY = sc.nextInt() - 1;int[][] B = new int[H][W];for (int i = 0; i < H; ++i) {char[] row = sc.next().toCharArray();for (int j = 0; j < W; ++j) {B[i][j] = row[j] - '0';}}boolean[][] visited = new boolean[H][W];visited[SX][SY] = true;ArrayList<Integer> q = new ArrayList<>();q.add((SX << 16) | SY);for (int i = 0; i < q.size(); ++i) {int cx = q.get(i) >> 16;int cy = q.get(i) & 0xFFFF;if (GX == cx && GY == cy) {System.out.println("YES");return;}for (int j = 0; j < 4; ++j) {int nx = cx + DX[j];int ny = cy + DY[j];if (nx < 0 || H <= nx || ny < 0 || W <= ny) continue;if (visited[nx][ny]) continue;if (Math.abs(B[cx][cy] - B[nx][ny]) <= 1) {visited[nx][ny] = true;q.add((nx << 16) | ny);}}for (int j = 0; j < 4; ++j) {int nx = cx + DX[j] * 2;int ny = cy + DY[j] * 2;if (nx < 0 || H <= nx || ny < 0 || W <= ny) continue;if (visited[nx][ny]) continue;if (B[cx][cy] == B[nx][ny] && B[cx][cy] > B[cx + DX[j]][cy + DY[j]]) {visited[nx][ny] = true;q.add((nx << 16) | ny);}}}System.out.println("NO");}}