結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2017-04-03 01:55:11 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,349 ms / 5,000 ms |
コード長 | 3,035 bytes |
コンパイル時間 | 998 ms |
コンパイル使用メモリ | 114,080 KB |
実行使用メモリ | 153,876 KB |
最終ジャッジ日時 | 2024-07-01 08:40:08 |
合計ジャッジ時間 | 19,935 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 P { static int Search(int goal) { Random r = new Random((int)DateTime.Now.Ticks); int x = 1; int c = 1; int step = 1; KeyValuePair<int, int> post; KeyValuePair<int, int> pre; path.Add(new KeyValuePair<int, int>(x, c)); minX[x] = Math.Min(1, c); memo[x][1] = true; if (x == goal) { return 1; } while (path.Count != 0) { if (x == goal) { return c; } else { KeyValuePair<int, int> p = path.First(); x = p.Key; c = p.Value; path.Remove(path.First()); step = Convert.ToString(x, 2).Replace("0", "").Length; post = new KeyValuePair<int, int>(x + step, c + 1); pre = new KeyValuePair<int, int>(x - step, c + 1); if (1 <= post.Key && post.Key <= goal) { if (!path.Contains(post)) { if (minX[post.Key] == -1) { minX[post.Key] = post.Value; } else { minX[post.Key] = Math.Min(minX[post.Key], post.Value); } if (!memo[x][post.Key]) { path.Add(new KeyValuePair<int, int>(post.Key, minX[post.Key])); memo[x][post.Key] = true; } } } if (1 <= pre.Key && pre.Key <= goal) { if (!path.Contains(pre)) { if (minX[pre.Key] == -1) { minX[pre.Key] = pre.Value; } else { minX[pre.Key] = Math.Min(minX[pre.Key], pre.Value); } if (!memo[x][pre.Key]) { path.Add(new KeyValuePair<int, int>(pre.Key, minX[pre.Key])); memo[x][pre.Key] = true; } } } } } return -1; } static bool[][] memo; static int[] minX; static List<KeyValuePair<int, int>> path = new List<KeyValuePair<int, int>>(); static void Main() { int n = int.Parse(Console.ReadLine()); memo = new bool[n+1][]; for (int i = 0; i < memo.Length; i++) { memo[i] = Enumerable.Range(0, n+1).Select(a => false).ToArray(); } minX = Enumerable.Range(0, n+1).Select(a => -1).ToArray(); Console.WriteLine(Search(n)); } }