using System; using System.Collections.Generic; using System.Linq; // https://yukicoder.me/problems/no/34 class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); 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 InputList = GetInputList(); int[] wkArr = { }; Action 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 Stack(); JyoutaiDef WillPush; WillPush.CurrX = Sx; WillPush.CurrY = Sy; WillPush.CurrV = V; WillPush.Level = 0; Stk.Push(WillPush); int AnswerLevel = int.MaxValue; bool FoundAnswer = false; var EdakiriInfoListDict = new Dictionary>(); while (Stk.Count > 0) { JyoutaiDef Popped = Stk.Pop(); //クリア処理 if (Popped.CurrX == Gx && Popped.CurrY == Gy) { FoundAnswer = true; if (AnswerLevel > Popped.Level) { AnswerLevel = Popped.Level; } continue; } Func DeriveGoalKyori = (pCurrX, pCurrY) => Math.Abs(Gx - pCurrX) + Math.Abs(Gy - pCurrY); Action 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.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(); } bool IsNG = false; 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.Push(WillPush); }; // ゴールまでのマンハッタン距離で処理を分岐 if (DeriveGoalKyori(Popped.CurrX, Popped.CurrY) > 1) { PushSyori(Popped.CurrX, Popped.CurrY - 1); PushSyori(Popped.CurrX, Popped.CurrY + 1); PushSyori(Popped.CurrX - 1, Popped.CurrY); PushSyori(Popped.CurrX + 1, Popped.CurrY); } else PushSyori(Gx, Gy); } Console.WriteLine(FoundAnswer ? AnswerLevel : -1); } }