using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); 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 InputList = GetInputList(); int[] wkArr = { }; Action 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 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[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 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"); } }