結果

問題 No.323 yuki国
ユーザー KilisameKilisame
提出日時 2016-09-15 16:08:13
言語 Java21
(openjdk 21)
結果
RE  
実行時間 -
コード長 3,923 bytes
コンパイル時間 3,073 ms
コンパイル使用メモリ 79,124 KB
実行使用メモリ 75,048 KB
最終ジャッジ日時 2024-04-28 13:50:29
合計ジャッジ時間 12,473 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 111 ms
40,436 KB
testcase_01 AC 107 ms
40,640 KB
testcase_02 AC 111 ms
40,560 KB
testcase_03 AC 115 ms
40,684 KB
testcase_04 AC 121 ms
41,196 KB
testcase_05 AC 127 ms
41,648 KB
testcase_06 AC 127 ms
41,580 KB
testcase_07 AC 129 ms
41,388 KB
testcase_08 AC 165 ms
56,876 KB
testcase_09 AC 444 ms
66,764 KB
testcase_10 AC 120 ms
41,184 KB
testcase_11 AC 120 ms
42,152 KB
testcase_12 RE -
testcase_13 AC 413 ms
66,556 KB
testcase_14 AC 155 ms
56,500 KB
testcase_15 AC 445 ms
67,444 KB
testcase_16 AC 710 ms
75,048 KB
testcase_17 AC 468 ms
66,956 KB
testcase_18 AC 166 ms
48,188 KB
testcase_19 AC 128 ms
47,032 KB
testcase_20 AC 231 ms
60,888 KB
testcase_21 AC 151 ms
56,368 KB
testcase_22 AC 412 ms
66,796 KB
testcase_23 AC 153 ms
64,576 KB
testcase_24 AC 285 ms
67,776 KB
testcase_25 AC 151 ms
56,624 KB
testcase_26 AC 271 ms
62,560 KB
testcase_27 AC 137 ms
52,388 KB
testcase_28 AC 446 ms
66,904 KB
testcase_29 AC 474 ms
66,728 KB
testcase_30 AC 119 ms
41,432 KB
testcase_31 AC 116 ms
41,600 KB
testcase_32 AC 118 ms
41,276 KB
testcase_33 AC 121 ms
41,528 KB
testcase_34 AC 122 ms
41,536 KB
testcase_35 AC 120 ms
41,208 KB
testcase_36 AC 112 ms
40,576 KB
testcase_37 AC 112 ms
40,396 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なので、ゴール時の要求サイズ+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