結果

問題 No.323 yuki国
ユーザー KilisameKilisame
提出日時 2016-09-15 16:11:36
言語 Java21
(openjdk 21)
結果
AC  
実行時間 582 ms / 5,000 ms
コード長 3,925 bytes
コンパイル時間 4,511 ms
コンパイル使用メモリ 74,976 KB
実行使用メモリ 68,792 KB
最終ジャッジ日時 2023-09-10 21:36:12
合計ジャッジ時間 14,792 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 129 ms
55,684 KB
testcase_01 AC 128 ms
55,820 KB
testcase_02 AC 127 ms
55,984 KB
testcase_03 AC 132 ms
56,120 KB
testcase_04 AC 129 ms
55,964 KB
testcase_05 AC 128 ms
55,576 KB
testcase_06 AC 128 ms
55,636 KB
testcase_07 AC 129 ms
56,080 KB
testcase_08 AC 139 ms
59,988 KB
testcase_09 AC 544 ms
65,860 KB
testcase_10 AC 128 ms
55,868 KB
testcase_11 AC 135 ms
55,524 KB
testcase_12 AC 134 ms
55,888 KB
testcase_13 AC 506 ms
65,636 KB
testcase_14 AC 138 ms
60,060 KB
testcase_15 AC 500 ms
65,760 KB
testcase_16 AC 573 ms
66,136 KB
testcase_17 AC 549 ms
65,536 KB
testcase_18 AC 183 ms
59,896 KB
testcase_19 AC 136 ms
57,892 KB
testcase_20 AC 207 ms
60,100 KB
testcase_21 AC 139 ms
60,104 KB
testcase_22 AC 428 ms
68,792 KB
testcase_23 AC 140 ms
60,000 KB
testcase_24 AC 292 ms
65,672 KB
testcase_25 AC 139 ms
60,412 KB
testcase_26 AC 275 ms
61,228 KB
testcase_27 AC 133 ms
55,972 KB
testcase_28 AC 579 ms
66,148 KB
testcase_29 AC 582 ms
66,364 KB
testcase_30 AC 129 ms
55,976 KB
testcase_31 AC 128 ms
55,656 KB
testcase_32 AC 128 ms
55,640 KB
testcase_33 AC 127 ms
55,524 KB
testcase_34 AC 132 ms
55,636 KB
testcase_35 AC 127 ms
53,716 KB
testcase_36 AC 126 ms
56,100 KB
testcase_37 AC 129 ms
55,708 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package puzzle.yukicoder.snowcountry;

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

public class SnowCountry {

    private static int h;

    private static int w;

    private static int[] start;

    private static int[] goal;

    private static boolean[][] blocksStatus;

    private static boolean[][][] checked;

    private static int maxSize;

    /*
     * スタートからゴールまでのマス数が奇数であれば、開始時の雪玉サイズと終了時の差が奇数でなければならず、マス数が偶数ならサイズ差も偶数である必要がある。まずこの条件を満たすことをチェックする。
     * スタートからゴールまでの最長距離はh+w-2なので、ゴール時の要求サイズ+h+w-2以上の大きさに雪玉が大きくなる必要はない。(ただし、開始のサイズ＋h+w-2までは拡大してしまう可能性がある)
     */
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        h = cin.nextInt();
        w = cin.nextInt();
        blocksStatus = new boolean[h][w];
        start = new int[3];
        start[0] = cin.nextInt();
        start[1] = cin.nextInt();
        start[2] = cin.nextInt();
        goal = new int[3];
        goal[0] = cin.nextInt();
        goal[1] = cin.nextInt();
        goal[2] = cin.nextInt();
        /* 探索済みの場合記録する */
        maxSize = Math.max(start[0], goal[0]) + h + w - 2;
        checked = new boolean[maxSize][h][w];
        cin.nextLine();
        for (int i = 0; i < h; i++) {
            char[] charArray = cin.nextLine().toCharArray();
            for (int j = 0; j < w; j++) {
                if (charArray[j] == '*') {
                    /* 雪ブロック */
                    blocksStatus[i][j] = true;
                }
            }
        }
        cin.close();
        /* 偶奇チェック */
        if ((start[0] + goal[0]) % 2 != (start[1] + start[2] + goal[1] + goal[2]) % 2) {
            exit(false);
        }
        /* Start地点から探索開始 */
        List<int[]> currentStep = new ArrayList<int[]>();
        currentStep.add(new int[] {start[0], start[1] - 1, start[2]});
        currentStep.add(new int[] {start[0], start[1] + 1, start[2]});
        currentStep.add(new int[] {start[0], start[1], start[2] - 1});
        currentStep.add(new int[] {start[0], start[1], start[2] + 1});
        while (!currentStep.isEmpty()) {
            List<int[]> nextStep = new ArrayList<int[]>();
            for (int[] step : currentStep) {
                nextStep.addAll(step(step));
            }
            currentStep = nextStep;
        }
        exit(false);
    }

    private static List<int[]> step(int[] block) {
        List<int[]> nextStep = new ArrayList<int[]>();
        if (block[1] < 0 || block[1] >= h || block[2] < 0 || block[2] >= w) {
            return nextStep;
        }
        if (checked[block[0]][block[1]][block[2]]) {
            return nextStep;
        }
        checked[block[0]][block[1]][block[2]] = true;
        if (blocksStatus[block[1]][block[2]]) {
            block[0]++;
        } else {
            block[0]--;
        }
        if (Arrays.equals(block, goal)) {
            exit(true);
        }
        if (block[0] == 0 || block[0] == maxSize) {
            return nextStep;
        }
        nextStep.add(new int[] {block[0], block[1] - 1, block[2]});
        nextStep.add(new int[] {block[0], block[1] + 1, block[2]});
        nextStep.add(new int[] {block[0], block[1], block[2] - 1});
        nextStep.add(new int[] {block[0], block[1], block[2] + 1});
        return nextStep;
    }

    private static void exit(boolean result) {
        if (result) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
        System.exit(0);
    }

}
0