結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2015-07-20 20:28:34 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 311 ms / 5,000 ms |
コード長 | 3,008 bytes |
コンパイル時間 | 2,765 ms |
コンパイル使用メモリ | 115,120 KB |
実行使用メモリ | 66,196 KB |
最終ジャッジ日時 | 2024-07-01 07:27:51 |
合計ジャッジ時間 | 6,521 ms |
ジャッジサーバーID (参考情報) |
judge1 / 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 = "Input4"; static List<string> GetInputList() { var WillReturn = new List<string>(); if (InputPattern == "Input1") { WillReturn.Add("5"); } else if (InputPattern == "Input2") { WillReturn.Add("11"); } else if (InputPattern == "Input3") { WillReturn.Add("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).ToCharArray().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); } }