結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 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);}}