第13回オフラインリアルタイムどう書くの参考問題。C#で解く。

• 増やす減らす二倍する 〜 横へな 2013.9.6 参考問題

をC#で解きました。幅優先探索です。

using System;
using System.Collections.Generic;

namespace Example {
    class MainClass {
        public static int Calc(int n) {
            var fns = new List<Func<int, int>> {
                x => x + 1,
                x => x - 1,
                x => x * 2,
            };

            var used = new HashSet<int>();
            var q = new Queue<Tuple<int, int>>();
            q.Enqueue(Tuple.Create(0, 0));
            used.Add(0);
            while (q.Count > 0) {
                var t = q.Dequeue();
                if (t.Item1 == n) return t.Item2;

                foreach (var fn in fns) {
                    int x = fn(t.Item1);                    
                    if (x <= 0 || used.Contains(x))
                        continue;

                    used.Add(x);
                    q.Enqueue(Tuple.Create(x, t.Item2 + 1));
                }
            }
            return -1;
        }

        public static void test(string input, string expect) {
            int answer = Calc(Convert.ToInt32(input));
            if (answer == Convert.ToInt32(expect)) {
                Console.WriteLine("OK");
            }
            else {
                Console.WriteLine("!!! NG !!!");
            }
        }

        public static void Main(string[] args) {
            /*0*/ test( "59", "9" );    
            /*1*/ test( "10", "5" );    
        }
    }
}