結果
問題 | No.3 ビットすごろく |
ユーザー | aketijyuuzou |
提出日時 | 2024-10-10 21:26:08 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 305 ms / 5,000 ms |
コード長 | 3,298 bytes |
コンパイル時間 | 974 ms |
コンパイル使用メモリ | 115,932 KB |
実行使用メモリ | 66,168 KB |
最終ジャッジ日時 | 2024-10-10 21:26:17 |
合計ジャッジ時間 | 6,817 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "InputX"; static List<string> GetInputList() { var WillReturn = new List<string>(); if (InputPattern == "Input1") { WillReturn.Add("5"); //4 //1->2->3->5 //という経路をたどります。 } else if (InputPattern == "Input2") { WillReturn.Add("11"); //1->2->3->5->7->10->8->9->11 //という経路をたどると9移動数で到達します。 } else if (InputPattern == "Input3") { WillReturn.Add("4"); //4つしかマスがないときは到達することは出来ません。 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct JyoutaiDef { internal int Level; internal int CurrInd; internal string Path; } static void Main() { List<string> InputList = GetInputList(); //すごろくのマスの数 int MasuCnt = int.Parse(InputList[0]); //各マスの1のビット数の配列 int[] BitCntArr = new int[MasuCnt]; for (int I = 1; I <= BitCntArr.GetUpperBound(0); I++) { int wkBitCnt = Convert.ToString(I, 2).Count(X => X == '1'); BitCntArr[I] = wkBitCnt; } //各マスごとの最短手数 var MinLevelDict = new Dictionary<int, int>(); var stk = new Stack<JyoutaiDef>(); JyoutaiDef WillPush; WillPush.Level = 1; WillPush.CurrInd = 1; WillPush.Path = "1"; stk.Push(WillPush); int AnswerLevel = int.MaxValue; bool FoundAnswer = false; while (stk.Count > 0) { JyoutaiDef Popped = stk.Pop(); int CurrInd = Popped.CurrInd; //クリア判定 if (CurrInd == MasuCnt) { FoundAnswer = true; AnswerLevel = Popped.Level; //Console.WriteLine("{0}手の解候補。{1}を発見", Popped.Level, Popped.Path); continue; } //レベル制限 if (AnswerLevel <= Popped.Level + 1) continue; //Push処理 Action<int> PushSyori = (pNewInd) => { if (pNewInd < 1) return; if (MasuCnt < pNewInd) return; WillPush.Level = Popped.Level + 1; WillPush.CurrInd = pNewInd; //各マスごとの最短手数でなければ枝切り if (MinLevelDict.ContainsKey(WillPush.CurrInd)) { if (MinLevelDict[WillPush.CurrInd] <= WillPush.Level) { return; } } MinLevelDict[WillPush.CurrInd] = WillPush.Level; WillPush.Path = Popped.Path + "->" + pNewInd.ToString(); stk.Push(WillPush); }; PushSyori(CurrInd - BitCntArr[CurrInd]); PushSyori(CurrInd + BitCntArr[CurrInd]); } Console.WriteLine(FoundAnswer ? AnswerLevel : -1); } }