yukicoder 0034 砂漠の行商人

■■■問題■■■

太郎君は砂漠を歩く行商人です。
太郎君はこれから次の街へ行こうとしています。

砂漠には移動しやすい場所とそうでない場所があり、
太郎君は長年の経験から、その場所に行くとどれくらいの体力を消耗するかを知っています。

砂漠は際限なく続いていますが、太郎君が知っているのはN×Nマスの範囲だけで、
その外側に行くと命の危険があるため絶対に行きません。

いま太郎君は体力Vで(Sx,Sy)の場所に立っており、次の街は(Gx,Gy)の場所にあります。
太郎君は、辺を共有する前後左右の隣接マスへのみ移動することができ、
今居るマスから隣のマスへ移動するときに1回の移動とみなし、
さらに、移動した先の砂漠レベル(Lxy)分の体力が減ります。
移動先の砂漠レベルが0の場合、体力値は減りませんが、
太郎君の体力が0以下になった時点で太郎君が死んでしまいます。
街に着いた瞬間に死んでしまってもいけません。

太郎君は、商品をできるだけ早く捌きたいので、
「太郎君が死なずに」「最も早く次の街へ着く」には、
どれくらい時間がかかるか計算してください。

■■■入力■■■

N V Sx Sy Gx Gy
L11 L21 L31 ・・・ Ln1
L12 L22 L32 ・・・ Ln2
・・・
L1n L2n L3n ・・・ Lnn

1行目に、砂漠の1辺の長さを表す整数N (3 <= N <= 100)、
太郎君の体力値を表す整数V (1 <= V <= 10000)、
太郎君の初期位置を表す整数の組 (Sx,Sy)(1 <= Sx,Sy <= N)、
次の街の位置を表す整数の組 (GX,GY)(1 <= Gx,Gy <= N)、
がスペース区切りで与えられます。
続くN行に、それぞれの場所の砂漠レベル Lxy (0 <= Lxy <= 9) が空白区切りで与えられます。

初期位置(Sx,Sy)と次の街の位置(Gx,Gy)は、同じ座標になることはありません。

■■■出力■■■

太郎君が死なずに、最も早く次の街へ着く最小の移動回数。
どうやっても生きてたどり着けない場合は -1 を出力すること。
最後に改行すること。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// https://yukicoder.me/problems/no/34
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 2 1 1 3 1");
            WillReturn.Add("0 2 0");
            WillReturn.Add("0 1 0");
            WillReturn.Add("0 0 0");
            //4
            //遠回りすれば体力を減らさずに着くことができますが、移動回数6が必要です。
            //(1,1)→(2,1)→(3,1) の順に歩くと移動回数2ですが、
            //途中で死んでしまうためダメです。
            //(1,1)→(1,2)→(2,2)→(3,2)→(3,1) の順に歩くのが、
            //死なない範囲で最も早く着くことができます。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 25 1 1 4 4");
            WillReturn.Add("0 1 3 3");
            WillReturn.Add("1 4 1 5");
            WillReturn.Add("2 2 7 8");
            WillReturn.Add("6 7 4 9");
            //-1
            //どのような経路でも途中で死んでしまうため、次の街へ着くことができません
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("21 40 15 1 18 21");
            WillReturn.Add("0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0");
            WillReturn.Add("9 4 3 9 0 4 4 3 0 8 7 0 2 2 2 3 8 1 2 1 2");
            WillReturn.Add("2 5 6 3 4 9 1 2 2 6 6 8 0 1 1 0 9 8 4 6 3");
            WillReturn.Add("6 5 0 7 9 9 7 2 9 4 3 0 9 7 5 9 0 4 1 9 5");
            WillReturn.Add("3 9 2 1 8 4 7 9 8 0 3 9 5 1 2 1 2 5 9 8 1");
            WillReturn.Add("0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0");
            WillReturn.Add("5 1 7 9 5 2 3 0 4 0 8 4 4 8 5 4 2 8 3 8 6");
            WillReturn.Add("3 9 6 7 3 0 4 1 9 5 1 2 2 3 0 8 0 6 6 4 4");
            WillReturn.Add("3 6 6 6 7 4 5 3 0 6 7 3 5 1 9 3 0 5 9 9 9");
            WillReturn.Add("8 1 1 4 2 5 9 3 2 4 1 8 4 6 3 5 5 3 3 6 4");
            WillReturn.Add("0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0");
            WillReturn.Add("5 5 7 7 9 2 8 4 5 6 4 6 8 2 7 3 5 8 5 2 4");
            WillReturn.Add("9 0 7 7 0 4 1 6 1 9 1 5 0 1 6 5 2 6 6 6 5");
            WillReturn.Add("3 9 7 7 2 6 3 7 1 5 3 8 9 5 6 3 4 8 7 3 4");
            WillReturn.Add("8 9 1 0 3 9 4 3 9 1 4 8 1 0 5 9 4 3 6 1 3");
            WillReturn.Add("0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0");
            WillReturn.Add("9 5 0 0 4 9 3 9 6 5 4 2 1 5 9 8 7 8 8 6 3");
            WillReturn.Add("7 2 3 9 9 9 7 7 0 5 8 0 6 3 6 1 2 3 1 0 5");
            WillReturn.Add("7 8 1 1 8 5 4 3 5 0 2 5 8 5 3 5 3 4 1 0 7");
            WillReturn.Add("7 1 8 1 2 0 5 8 1 3 9 6 1 3 8 3 9 4 8 6 8");
            WillReturn.Add("0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0");
            //33
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal int CurrV;
        internal int Level;
    }

    // 枝切りで使う情報
    struct EdakiriInfo
    {
        internal int CurrV;
        internal int Level;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = (pStr) =>
            wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();

        SplitAct(InputList[0]);
        int N = wkArr[0];
        int V = wkArr[1];
        int Sx = wkArr[2], Sy = wkArr[3];
        int Gx = wkArr[4], Gy = wkArr[5];

        int[,] SabakuArr = new int[N + 1, N + 1];
        for (int Y = 1; Y <= N; Y++) {
            SplitAct(InputList[Y]);
            for (int X = 1; X <= N; X++) {
                SabakuArr[X, Y] = wkArr[X - 1];
            }
        }

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrX = Sx; WillEnqueue.CurrY = Sy;
        WillEnqueue.CurrV = V;
        WillEnqueue.Level = 0;
        Que.Enqueue(WillEnqueue);

        int AnswerLevel = int.MaxValue;
        bool FoundAnswer = false;

        var EdakiriInfoListDict = new Dictionary<int, List<EdakiriInfo>>();

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            //クリア処理
            if (Dequeued.CurrX == Gx && Dequeued.CurrY == Gy) {
                FoundAnswer = true;
                if (AnswerLevel > Dequeued.Level) {
                    AnswerLevel = Dequeued.Level;
                }
                continue;
            }

            Func<int, int, int> DeriveGoalKyori = (pCurrX, pCurrY) =>
                Math.Abs(Gx - pCurrX)
              + Math.Abs(Gy - pCurrY);

            Action<int, int> EnqueueAct = (pNewX, pNewY) =>
            {
                if (pNewX < 1 || N < pNewX) return;
                if (pNewY < 1 || N < pNewY) return;

                WillEnqueue.CurrX = pNewX;
                WillEnqueue.CurrY = pNewY;
                WillEnqueue.CurrV = Dequeued.CurrV - SabakuArr[pNewX, pNewY];
                if (WillEnqueue.CurrV <= 0) return;
                WillEnqueue.Level = Dequeued.Level + 1;

                // 下限値枝切り
                if (FoundAnswer) {
                    if (AnswerLevel <= WillEnqueue.Level
                                     + DeriveGoalKyori(WillEnqueue.CurrX, WillEnqueue.CurrY))
                        return;
                }

                // 枝切り
                int Hash = WillEnqueue.CurrX * 1000 + WillEnqueue.CurrY;
                if (EdakiriInfoListDict.ContainsKey(Hash) == false) {
                    EdakiriInfoListDict[Hash] = new List<EdakiriInfo>();
                }

                bool IsNG = false;
                for (int I = EdakiriInfoListDict[Hash].Count - 1; 0 <= I; I--) {
                    if (EdakiriInfoListDict[Hash][I].CurrV >= WillEnqueue.CurrV &&
                        EdakiriInfoListDict[Hash][I].Level <= WillEnqueue.Level) {
                        IsNG = true;
                        break;
                    }
                    if (EdakiriInfoListDict[Hash][I].CurrV <= WillEnqueue.CurrV &&
                        EdakiriInfoListDict[Hash][I].Level >= WillEnqueue.Level) {
                        EdakiriInfoListDict[Hash].RemoveAt(I);
                    }
                }
                if (IsNG) return;

                EdakiriInfo WillAdd;
                WillAdd.CurrV = WillEnqueue.CurrV;
                WillAdd.Level = WillEnqueue.Level;
                EdakiriInfoListDict[Hash].Add(WillAdd);

                Que.Enqueue(WillEnqueue);
            };

            EnqueueAct(Dequeued.CurrX, Dequeued.CurrY - 1);
            EnqueueAct(Dequeued.CurrX, Dequeued.CurrY + 1);
            EnqueueAct(Dequeued.CurrX - 1, Dequeued.CurrY);
            EnqueueAct(Dequeued.CurrX + 1, Dequeued.CurrY);
        }
        Console.WriteLine(FoundAnswer ? AnswerLevel : -1);
    }
}

解説

枝切り多めなBFSで解いてます。