結果

問題 No.323 yuki国
ユーザー KilisameKilisame
提出日時 2016-09-15 16:11:36
言語 Java21
(openjdk 21)
結果
AC  
実行時間 576 ms / 5,000 ms
コード長 3,925 bytes
コンパイル時間 3,848 ms
コンパイル使用メモリ 78,700 KB
実行使用メモリ 56,532 KB
最終ジャッジ日時 2024-06-28 12:38:51
合計ジャッジ時間 13,875 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 142 ms
42,088 KB
testcase_01 AC 125 ms
40,492 KB
testcase_02 AC 144 ms
41,640 KB
testcase_03 AC 146 ms
42,056 KB
testcase_04 AC 142 ms
41,876 KB
testcase_05 AC 142 ms
41,960 KB
testcase_06 AC 141 ms
41,960 KB
testcase_07 AC 145 ms
41,508 KB
testcase_08 AC 143 ms
47,356 KB
testcase_09 AC 503 ms
53,672 KB
testcase_10 AC 143 ms
41,516 KB
testcase_11 AC 148 ms
42,348 KB
testcase_12 AC 148 ms
42,320 KB
testcase_13 AC 465 ms
53,316 KB
testcase_14 AC 155 ms
48,508 KB
testcase_15 AC 518 ms
53,960 KB
testcase_16 AC 576 ms
53,948 KB
testcase_17 AC 517 ms
53,484 KB
testcase_18 AC 193 ms
47,032 KB
testcase_19 AC 147 ms
44,456 KB
testcase_20 AC 227 ms
48,328 KB
testcase_21 AC 156 ms
48,596 KB
testcase_22 AC 406 ms
56,532 KB
testcase_23 AC 156 ms
48,168 KB
testcase_24 AC 301 ms
53,080 KB
testcase_25 AC 155 ms
48,376 KB
testcase_26 AC 288 ms
49,444 KB
testcase_27 AC 149 ms
42,028 KB
testcase_28 AC 551 ms
53,592 KB
testcase_29 AC 533 ms
53,396 KB
testcase_30 AC 128 ms
40,664 KB
testcase_31 AC 143 ms
41,984 KB
testcase_32 AC 140 ms
41,832 KB
testcase_33 AC 139 ms
41,536 KB
testcase_34 AC 147 ms
41,664 KB
testcase_35 AC 141 ms
41,692 KB
testcase_36 AC 142 ms
41,832 KB
testcase_37 AC 142 ms
41,552 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