ABC093-C Same Integers

問題へのリンク

C#のソース

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("2 5 4");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 6 3");
            //5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("31 41 5");
            //23
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal int CurrA;
        internal int CurrB;
        internal int CurrC;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int A = wkArr[0];
        int B = wkArr[1];
        int C = wkArr[2];

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.Level = 0;
        WillEnqueue.CurrA = A;
        WillEnqueue.CurrB = B;
        WillEnqueue.CurrC = C;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<string>();

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            if (Dequeued.CurrA == Dequeued.CurrB && Dequeued.CurrA == Dequeued.CurrC) {
                Console.WriteLine(Dequeued.Level);
                return;
            }

            Action<int, int, int> EnqueueAct = (pNewA, pNewB, pNewC) =>
            {
                string Hash = string.Format("{0},{1},{2}", pNewA, pNewB, pNewC);
                if (VisitedSet.Add(Hash) == false) return;

                WillEnqueue.Level = Dequeued.Level + 1;
                WillEnqueue.CurrA = pNewA;
                WillEnqueue.CurrB = pNewB;
                WillEnqueue.CurrC = pNewC;
                Que.Enqueue(WillEnqueue);
            };

            EnqueueAct(Dequeued.CurrA, Dequeued.CurrB + 1, Dequeued.CurrC + 1);
            EnqueueAct(Dequeued.CurrA, Dequeued.CurrB, Dequeued.CurrC + 2);
            EnqueueAct(Dequeued.CurrA, Dequeued.CurrB + 2, Dequeued.CurrC);
            EnqueueAct(Dequeued.CurrA, Dequeued.CurrB + 1, Dequeued.CurrC + 1);
            EnqueueAct(Dequeued.CurrA + 1, Dequeued.CurrB, Dequeued.CurrC + 1);
            EnqueueAct(Dequeued.CurrA + 1, Dequeued.CurrB + 1, Dequeued.CurrC);
            EnqueueAct(Dequeued.CurrA + 2, Dequeued.CurrB, Dequeued.CurrC);
        }
    }
}

解説

3つの値の組合せをハッシュ値として
再訪防止をした幅優先探索で解いてます。