結果

問題 No.34 砂漠の行商人
コンテスト
ユーザー yuki2006
提出日時 2014-10-05 23:35:46
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 3,228 bytes
コンパイル時間 4,914 ms
コンパイル使用メモリ 78,072 KB
実行使用メモリ 807,972 KB
最終ジャッジ日時 2024-12-30 07:12:16
合計ジャッジ時間 94,219 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 13 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

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