結果

問題 No.3 ビットすごろく
ユーザー masakt
提出日時 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.

ソースコード

diff # 

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));
    }
}
0