結果
問題 | No.34 砂漠の行商人 |
ユーザー | 明智重蔵 |
提出日時 | 2022-07-30 09:50:24 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,381 ms / 5,000 ms |
コード長 | 7,152 bytes |
コンパイル時間 | 1,053 ms |
コンパイル使用メモリ | 66,500 KB |
実行使用メモリ | 30,500 KB |
最終ジャッジ日時 | 2023-09-27 11:19:27 |
合計ジャッジ時間 | 8,823 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 68 ms
21,816 KB |
testcase_01 | AC | 68 ms
21,936 KB |
testcase_02 | AC | 70 ms
23,920 KB |
testcase_03 | AC | 69 ms
21,964 KB |
testcase_04 | AC | 121 ms
28,304 KB |
testcase_05 | AC | 125 ms
28,432 KB |
testcase_06 | AC | 75 ms
24,012 KB |
testcase_07 | AC | 191 ms
29,104 KB |
testcase_08 | AC | 228 ms
27,160 KB |
testcase_09 | AC | 465 ms
29,476 KB |
testcase_10 | AC | 103 ms
28,788 KB |
testcase_11 | AC | 160 ms
27,716 KB |
testcase_12 | AC | 84 ms
26,188 KB |
testcase_13 | AC | 1,381 ms
29,548 KB |
testcase_14 | AC | 941 ms
28,788 KB |
testcase_15 | AC | 72 ms
24,024 KB |
testcase_16 | AC | 117 ms
28,240 KB |
testcase_17 | AC | 70 ms
21,980 KB |
testcase_18 | AC | 73 ms
21,908 KB |
testcase_19 | AC | 373 ms
27,504 KB |
testcase_20 | AC | 561 ms
27,824 KB |
testcase_21 | AC | 72 ms
21,928 KB |
testcase_22 | AC | 76 ms
23,980 KB |
testcase_23 | AC | 72 ms
23,960 KB |
testcase_24 | AC | 690 ms
30,500 KB |
testcase_25 | AC | 103 ms
26,244 KB |
ソースコード
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); } }