結果

問題 No.424 立体迷路
ユーザー thaim24thaim24
提出日時 2016-09-22 23:32:14
言語 Java
(openjdk 23)
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 3,299 bytes
コンパイル時間 3,784 ms
コンパイル使用メモリ 84,312 KB
実行使用メモリ 41,772 KB
最終ジャッジ日時 2024-07-05 07:06:57
合計ジャッジ時間 7,962 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class No424 {
    static final int[][] move = {
            {0, 1},
            {-1, 0},
            {0, -1},
            {1, 0}
    };
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int h = sc.nextInt();
        int w = sc.nextInt();

        int[] pos = new int[4];
        pos[0] = sc.nextInt();
        pos[1] = sc.nextInt();
        pos[2] = sc.nextInt();
        pos[3] = sc.nextInt();

        String[] b = new String[h];
        for (int i=0; i<h; i++) {
            b[i] = sc.next();
        }
        int[][] board = new int[h+2][w+2];
        for (int i=1; i<=h; i++) {
            for (int j=1; j<=w; j++) {
                board[i][j] = b[i-1].charAt(j-1) - '0';
            }
        }

        String result = solve(h, w, pos, board);

        System.out.println(result);
    }

    public static String solve(int h, int w, int[] pos, int[][] board) {
        boolean[][] reachable = new boolean[h+2][w+2];

        reachable[pos[0]][pos[1]] = true;
        List<Pos> list = new ArrayList<Pos>();
        list.add(new Pos(pos[0], pos[1]));

        while (!reachable[pos[2]][pos[3]] && list.size() > 0) {
            Pos current = list.remove(0);
//            System.err.println("current:" + current.toString());
            for (int i=0; i<4; i++) {
                Pos next = new Pos(current.x + move[i][0], current.y + move[i][1]);
                Pos next2 = new Pos(next.x + move[i][0], next.y + move[i][1]);
//                System.err.println("\tmove:" + move[i][0] + ", " + move[i][1] + ", next:" + next + ", next2:" + next2);

                if (next.x> h || next.x == 0
                        || next.y > w
                        || next.y == 0) {
                    continue;
                }

//                System.err.println("\tcheck start");
                if (!reachable[next.x][next.y] &&
                        Math.abs(board[current.x][current.y]-board[next.x][next.y]) <= 1) {
                    reachable[next.x][next.y] = true;
//                    System.err.println("\tboard: current=" + board[current.x][current.y] + ", next=" + board[next.x][next.y]);
                    list.add(next);
//                    System.err.println(next);
                }

//                System.err.println("\tcheck2 start");
                if (board[current.x][current.y] > board[next.x][next.y]
                        && next2.x <= h && next2.x > 0
                        && next2.y <= w && next2.y > 0
                        && !reachable[next2.x][next2.y]
                        && board[current.x][current.y] == board[next2.x][next2.y]) {
                    reachable[next2.x][next2.y] = true;
                    list.add(new Pos(next2.x, next2.y));
//                    System.err.println(next2);
                }
            }
        }

        if (reachable[pos[2]][pos[3]]) {
            return "YES";
        } else {
            return "NO";
        }
    }

    public static class Pos {
        int x;
        int y;
        public Pos(int a, int b) {
            x = a;
            y = b;
        }

        public String toString() {
            return "(" + x + ", " + y + ")";
        }
    }
}
0