結果

問題 No.34 砂漠の行商人
ユーザー 明智重蔵明智重蔵
提出日時 2022-07-30 09:30:59
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,236 ms / 5,000 ms
コード長 10,149 bytes
コンパイル時間 1,090 ms
コンパイル使用メモリ 70,696 KB
実行使用メモリ 31,744 KB
最終ジャッジ日時 2023-09-27 10:52:11
合計ジャッジ時間 8,372 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 63 ms
19,992 KB
testcase_01 AC 64 ms
22,108 KB
testcase_02 AC 62 ms
21,916 KB
testcase_03 AC 63 ms
19,924 KB
testcase_04 AC 109 ms
28,320 KB
testcase_05 AC 114 ms
26,368 KB
testcase_06 AC 70 ms
23,988 KB
testcase_07 AC 174 ms
26,992 KB
testcase_08 AC 200 ms
29,284 KB
testcase_09 AC 419 ms
29,496 KB
testcase_10 AC 93 ms
28,908 KB
testcase_11 AC 141 ms
27,820 KB
testcase_12 AC 75 ms
26,280 KB
testcase_13 AC 1,236 ms
31,744 KB
testcase_14 AC 845 ms
30,948 KB
testcase_15 AC 67 ms
22,108 KB
testcase_16 AC 105 ms
26,280 KB
testcase_17 AC 67 ms
22,100 KB
testcase_18 AC 67 ms
21,980 KB
testcase_19 AC 333 ms
27,500 KB
testcase_20 AC 503 ms
27,928 KB
testcase_21 AC 68 ms
22,000 KB
testcase_22 AC 70 ms
24,040 KB
testcase_23 AC 63 ms
22,112 KB
testcase_24 AC 622 ms
30,624 KB
testcase_25 AC 93 ms
24,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 if (InputPattern == "Input4") {
            return System.IO.File.ReadAllLines(@"D:\CSharp\TestConsole\ukicoderのテストデータ.txt").ToList();
            //198
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    // 枝切りで使う情報
    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 Stk = new Queue<PQueue.PQueueJyoutaiDef>();
        PQueue.PQueueJyoutaiDef WillPush;
        WillPush.CurrX = Sx; WillPush.CurrY = Sy;
        WillPush.CurrV = V;
        WillPush.Level = 0;
        Stk.Enqueue(WillPush);

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

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

        while (Stk.Count > 0) {
            PQueue.PQueueJyoutaiDef Popped = Stk.Dequeue();

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

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

            Action<int, int> PushAct = (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.Level = Popped.Level + 1;

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

                // 枝切り
                int Hash = WillPush.CurrX * 1000 + WillPush.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 >= WillPush.CurrV &&
                        EdakiriInfoListDict[Hash][I].Level <= WillPush.Level) {
                        IsNG = true;
                        break;
                    }
                    if (EdakiriInfoListDict[Hash][I].CurrV <= WillPush.CurrV &&
                        EdakiriInfoListDict[Hash][I].Level >= WillPush.Level) {
                        EdakiriInfoListDict[Hash].RemoveAt(I);
                    }
                }

                //foreach (EdakiriInfo EachEdakiriInfo in EdakiriInfoListDict[Hash]) {
                //    if (EachEdakiriInfo.CurrV >= WillPush.CurrV && EachEdakiriInfo.Level <= WillPush.Level) {
                //        IsNG = true;
                //        break;
                //    }
                //}
                if (IsNG) return;

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

                // メモ化探索
                Stk.Enqueue(WillPush);
            };

            // ゴールまでのマンハッタン距離で処理を分岐
            if (DeriveGoalKyori(Popped.CurrX, Popped.CurrY) > 1) {
                PushAct(Popped.CurrX, Popped.CurrY - 1);
                PushAct(Popped.CurrX, Popped.CurrY + 1);
                PushAct(Popped.CurrX - 1, Popped.CurrY);
                PushAct(Popped.CurrX + 1, Popped.CurrY);
            }
            else PushAct(Gx, Gy);
        }
        Console.WriteLine(FoundAnswer ? AnswerLevel : -1);
    }
}

#region PQueue
// 優先度付きキュー (根のValが最小)
internal class PQueue
{
    internal struct PQueueJyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal int CurrV;
        internal int Level;
    }

    private Dictionary<int, PQueueJyoutaiDef> mHeapDict = new Dictionary<int, PQueueJyoutaiDef>();

    internal bool IsEmpty()
    {
        return mHeapDict.Count == 0;
    }

    internal long Count()
    {
        return mHeapDict.Count;
    }

    internal long Peek()
    {
        return mHeapDict[1].Level;
    }

    // エンキュー処理
    internal void Enqueue(PQueueJyoutaiDef pAddJyoutai)
    {
        int CurrNode = 1 + mHeapDict.Count;
        mHeapDict[CurrNode] = pAddJyoutai;

        while (1 < CurrNode && mHeapDict[CurrNode / 2].Level > mHeapDict[CurrNode].Level) {
            PQueueJyoutaiDef Swap = mHeapDict[CurrNode];
            mHeapDict[CurrNode] = mHeapDict[CurrNode / 2];
            mHeapDict[CurrNode / 2] = Swap;

            CurrNode /= 2;
        }
    }

    // デキュー処理
    internal PQueueJyoutaiDef Dequeue()
    {
        PQueueJyoutaiDef TopNode = mHeapDict[1];
        int LastNode = mHeapDict.Count;
        mHeapDict[1] = mHeapDict[LastNode];
        mHeapDict.Remove(LastNode);

        MinHeapify(1);
        return TopNode;
    }

    // 根ノードを指定し、根から葉へヒープ構築
    private void MinHeapify(int pRootNode)
    {
        if (mHeapDict.Count <= 1) {
            return;
        }

        int Left = pRootNode * 2;
        int Right = pRootNode * 2 + 1;

        // 左の子、自分、右の子で値が最小のノードを選ぶ
        long Smallest = mHeapDict[pRootNode].Level;
        int SmallestNode = pRootNode;

        if (mHeapDict.ContainsKey(Left) && mHeapDict[Left].Level < Smallest) {
            Smallest = mHeapDict[Left].Level;
            SmallestNode = Left;
        }
        if (mHeapDict.ContainsKey(Right) && mHeapDict[Right].Level < Smallest) {
            Smallest = mHeapDict[Right].Level;
            SmallestNode = Right;
        }

        // 子ノードのほうが小さい場合
        if (SmallestNode != pRootNode) {
            PQueueJyoutaiDef Swap = mHeapDict[SmallestNode];
            mHeapDict[SmallestNode] = mHeapDict[pRootNode];
            mHeapDict[pRootNode] = Swap;

            // 再帰的に呼び出し
            MinHeapify(SmallestNode);
        }
    }
}
#endregion
0