No.20 砂漠のオアシス

■■■問題■■■

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

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

砂漠は際限なく続いていますが、太郎君が知っているのは N×Nマスの範囲だけで、
その外側に行くと命の危険があるため絶対に行きません。
砂漠の中には、(Ox,Oy)の場所にオアシスがありこの場所へ行くと、
「1度だけ」体力を現在の値の「2倍」にすることができます。(オアシスが無い場合もあります)

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

オアシスがある場所にも砂漠レベルが1以上ある場合もあり、
その場合は砂漠レベル分の体力が減った後に、オアシスの効果が適用されます。

太郎君が次の街へ無事たどり着けるか教えてあげてください。

■■■入力■■■

N V Ox Oy
L11 L21 L31 ・・・ LN1
L12 L22 L32 ・・・ LN2
・・・
L1N L2N L3N ・・・ LNN

1行目に、
砂漠の1辺の長さを表す整数N (2 <= N <= 200)、
太郎君の体力値を表す整数V (1 <= V <= 500)、
オアシスの位置を表す整数の組N (1 <= Ox,Oy <= N、または Ox=Oy=0 : オアシス無し)
がスペース区切りで与えられる。
2行目以降は
0 <= Lxy <= 9:(x,y)の場所の砂漠レベル(1 <= x,y <= N)
が半角スペース区切りで与えられる。

■■■出力■■■

たどり着けるなら「YES」、たどり着けないなら「NO」を出力してください。 (括弧は含まない)
最後に改行してください。

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3 3 0 0");
            WillReturn.Add("0 1 1");
            WillReturn.Add("2 0 1");
            WillReturn.Add("1 2 0");
            //YES
            //Ox=0 かつ Oy=0 なので、この場合オアシスはありません。
            //(1,1)→(2,1)→(2,2)→(3,2)→(3,3) の順に歩くのが最も体力を減らさずに行けます。
            //必要となる体力は2なので、目的地にたどり着くことができます。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 3 8 6");
            WillReturn.Add("0 9 0 0 0 9 0 0 0 9");
            WillReturn.Add("0 9 0 9 0 0 0 9 0 0");
            WillReturn.Add("0 9 0 9 9 9 9 9 9 0");
            WillReturn.Add("0 9 0 9 0 0 0 9 0 0");
            WillReturn.Add("0 9 0 9 0 9 0 0 9 0");
            WillReturn.Add("0 9 0 0 0 0 9 1 9 0");
            WillReturn.Add("0 9 9 0 9 9 9 9 0 0");
            WillReturn.Add("0 9 0 0 0 0 0 0 9 0");
            WillReturn.Add("0 9 9 9 9 9 9 0 9 1");
            WillReturn.Add("0 0 0 0 0 0 0 0 9 2");
            //YES
            //途中までは砂漠レベルが0 のマスを通って行けるので、
            //まったく減らさずに行けますが、
            //目的地直前で体力が合計3 減るため、
            //途中でオアシスによって行かなければなりません。
            //オアシスに寄ると、体力が3から1減り
            //さらにオアシス効果により2倍となるため、体力が4になります。
            //そのため、目的地にたどり着くことができます。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 30 8 8");
            WillReturn.Add("0 1 1 9 7 6 1 1 1 1");
            WillReturn.Add("1 5 1 4 6 7 1 1 3 1");
            WillReturn.Add("1 1 5 6 6 6 1 1 0 1");
            WillReturn.Add("0 1 5 6 7 1 0 7 9 1");
            WillReturn.Add("2 1 5 6 7 1 9 8 1 1");
            WillReturn.Add("1 1 5 5 5 0 9 9 1 5");
            WillReturn.Add("1 1 4 5 4 1 9 9 2 1");
            WillReturn.Add("1 2 3 4 1 0 9 9 4 6");
            WillReturn.Add("5 1 2 1 1 1 9 8 1 2");
            WillReturn.Add("1 1 1 1 1 1 9 3 9 1");
            //NO
        }
        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 bool UsedOashisu;
        internal string Path;
    }

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

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

        SplitAct(InputList[0]);
        int N = wkArr[0];
        int V = wkArr[1];
        int Ox = wkArr[2];
        int Oy = wkArr[3];

        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 stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrX = WillPush.CurrY = 1;
        WillPush.CurrV = V;
        WillPush.UsedOashisu = false;
        WillPush.Path = "(1,1)";
        stk.Push(WillPush);

        //体力[オアシス使用有無,X座標,Y座標]なメモ
        var MemoArr = new Nullable<int>[2, N + 1, N + 1];
        MemoArr[0, 1, 1] = WillPush.CurrV;

        bool FoundAnswer = false;

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア処理
            if (Popped.CurrX == N && Popped.CurrY == N) {
                FoundAnswer = true;
                Console.WriteLine("解を発見。{0}", Popped.Path);
                break;
            }

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

                WillPush.CurrX = pNewX;
                WillPush.CurrY = pNewY;
                WillPush.CurrV = Popped.CurrV - SabakuArr[pNewX, pNewY];
                if (WillPush.CurrV <= 0) return;

                WillPush.UsedOashisu = Popped.UsedOashisu;

                //オアシスの場合
                if (WillPush.UsedOashisu == false && pNewX == Ox && pNewY == Oy) {
                    WillPush.UsedOashisu = true;
                    WillPush.CurrV *= 2;
                }

                //メモ化再帰
                int IntUsedOashisu = (WillPush.UsedOashisu ? 1 : 0);
                if (MemoArr[IntUsedOashisu, pNewX, pNewY] != null) {
                    if (MemoArr[IntUsedOashisu, pNewX, pNewY].Value >= WillPush.CurrV)
                        return;
                }
                MemoArr[IntUsedOashisu, pNewX, pNewY] = WillPush.CurrV;

                WillPush.Path = Popped.Path + string.Format("-({0},{1})", pNewX, pNewY);

                stk.Push(WillPush);
            };

            PushSyori(Popped.CurrX, Popped.CurrY - 1);
            PushSyori(Popped.CurrX, Popped.CurrY + 1);
            PushSyori(Popped.CurrX - 1, Popped.CurrY);
            PushSyori(Popped.CurrX + 1, Popped.CurrY);
        }
        Console.WriteLine(FoundAnswer ? "YES" : "NO");
    }
}

デバッグ情報付の実行結果

解を発見。(1,1)-(2,1)-(2,2)-(3,2)-(3,3)
YES

解説

体力[オアシス使用有無,X座標,Y座標]をメモする、
メモ化探索で解いてます。