結果

問題 No.34 砂漠の行商人
ユーザー yuki2006yuki2006
提出日時 2014-10-05 23:35:46
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 3,228 bytes
コンパイル時間 3,083 ms
コンパイル使用メモリ 74,748 KB
実行使用メモリ 413,588 KB
最終ジャッジ日時 2023-08-28 20:08:38
合計ジャッジ時間 14,517 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 118 ms
55,648 KB
testcase_01 AC 122 ms
55,920 KB
testcase_02 AC 208 ms
79,612 KB
testcase_03 AC 210 ms
71,516 KB
testcase_04 AC 462 ms
160,036 KB
testcase_05 AC 489 ms
204,376 KB
testcase_06 WA -
testcase_07 AC 596 ms
261,432 KB
testcase_08 AC 824 ms
413,588 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.LinkedList;
import java.util.Scanner;

public class Yuki0XX_Nao3 {
    public static void main(String[] args) {
        Yuki0XX_Nao3 p = new Yuki0XX_Nao3();

    }

    final int[][] matrix;

    final int N;
    final int V;

    final int SX;
    final int SY;

    final int GX;
    final int GY;


    int getDamage(int x, int y) {
        return matrix[y][x];
    }


    public Yuki0XX_Nao3() {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        V = scanner.nextInt();


        SX = scanner.nextInt();
        SY = scanner.nextInt();

        GX = scanner.nextInt();
        GY = scanner.nextInt();


        matrix = new int[N][N];


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }
        System.out.println(solve());

    }

    class Status {
        int x;
        int y;

        public Status(int x, int y) {
            this.x = x;
            this.y = y;

        }
    }

    int[] vecX = {1, 0, -1, 0};
    int[] vecY = {0, 1, 0, -1};


    public int solve() {

        LinkedList<Status> queue = new LinkedList<Status>();
        queue.add(new Status(SX - 1, SY - 1));
        int[][][] dp = new int[N + 1][N + 1][10000];
        dp[SX - 1][SY - 1][getDamage(SX - 1, SY - 1)] = 1;

        while (queue.size() > 0) {
            final Status current = queue.pop();

            int x = current.x;
            int y = current.y;


            for (int i = 0; i < vecX.length; i++) {
                int x2 = x + vecX[i];
                int y2 = y + vecY[i];
                if (0 <= x2 && x2 < N && 0 <= y2 && y2 < N) {
                    boolean isFound = false;
                    //ダメージがVになると死ぬので　V-1からその時のダメージまでのもらうDP
                    for (int d = V - 1; d >= getDamage(x2, y2); d--) {
                        int v = 1 + dp[x][y][d - getDamage(x2, y2)];
                        //次の移動で1回目の移動ということはない
                        if (v == 1) {
                            continue;
                        }
                        //次の移動で最小移動数が更新できるのなら、更新する。
                        //また、一つでもあれば次の場所をキューに入れる。
                        if (dp[x2][y2][d] == 0 || dp[x2][y2][d] > v) {
                            dp[x2][y2][d] = v;
                            isFound = true;
                        }
                    }
                    //次の遷移が可能なものがあればキューに入れる。
                    if (isFound) {
                        queue.add(new Status(x2, y2));

                    }
                }
            }
        }
        int min = Integer.MAX_VALUE;
        //ゴールに関して各合計ダメージでの最小を探す。
        for (int d = 0; d <= V; d++) {
            if (dp[GX - 1][GY - 1][d] != 0) {
                min = Math.min(dp[GX - 1][GY - 1][d], min);
            }
        }
        if (min == Integer.MAX_VALUE) {
            return -1;
        }
        return min - 1;
    }
}
0