AOJ 0503 Cup

問題へのリンク

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("3 10");
            WillReturn.Add("0");
            WillReturn.Add("1 1");
            WillReturn.Add("2 2 3");
            WillReturn.Add("4 20");
            WillReturn.Add("2 1 2");
            WillReturn.Add("1 3");
            WillReturn.Add("1 4");
            WillReturn.Add("2 5");
            WillReturn.Add("2 1 2");
            WillReturn.Add("0");
            WillReturn.Add("0");
            WillReturn.Add("3 3");
            WillReturn.Add("0");
            WillReturn.Add("1 1");
            WillReturn.Add("2 2 3");
            WillReturn.Add("0 0");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mCupCnt;
    static int mLimitCnt;

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

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        int CurrInd = 0;
        while (true) {
            SplitAct(InputList[CurrInd]);

            mCupCnt = wkArr[0];
            mLimitCnt = wkArr[1];

            if (mCupCnt == 0 && mLimitCnt == 0) break;

            Solve(InputList.Skip(CurrInd + 1).Take(3).ToArray());
            CurrInd += 3 + 1;
        }
    }

    // 2べきな値[コップ番号]なDict
    static Dictionary<int, int> mBitValDict = new Dictionary<int, int>();

    static void Solve(string[] pInitArr)
    {
        mBitValDict.Clear();
        int Beki2Val = 1;
        for (int I = 1; I <= mCupCnt; I++) {
            mBitValDict[I] = Beki2Val;
            Beki2Val *= 2;
        }

        Func<string, int> GetBitVal = (pStr) =>
        {
            int[] IntArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
            if (IntArr.Length == 0) return 0;

            int ReturnVal = 0;
            foreach (int EachInt in IntArr.Skip(1)) {
                ReturnVal += mBitValDict[EachInt];
            }
            return ReturnVal;
        };

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.BitSet1 = GetBitVal(pInitArr[0]);
        WillEnqueue.BitSet2 = GetBitVal(pInitArr[1]);
        WillEnqueue.BitSet3 = GetBitVal(pInitArr[2]);
        WillEnqueue.Level = 0;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<long>();

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();
            //Console.WriteLine("Level={0},BitSet1={1},BitSet2={2},BitSet3={3}",
            //    Dequeued.Level, Dequeued.BitSet1, Dequeued.BitSet2, Dequeued.BitSet3);

            // クリア判定
            if (Dequeued.BitSet1 == 0 && Dequeued.BitSet2 == 0
             || Dequeued.BitSet2 == 0 && Dequeued.BitSet3 == 0) {
                Console.WriteLine(Dequeued.Level);
                return;
            }
            if (Dequeued.Level == mLimitCnt) {
                continue;
            }

            Action<int, int> EnqueueAct = (pFromPos, pToPos) =>
            {
                var BitSetDict = new Dictionary<int, int>();
                BitSetDict[1] = Dequeued.BitSet1;
                BitSetDict[2] = Dequeued.BitSet2;
                BitSetDict[3] = Dequeued.BitSet3;

                var Bit2ListDict = new Dictionary<int, List<int>>();
                Bit2ListDict[1] = DeriveBeki2List(BitSetDict[1]);
                Bit2ListDict[2] = DeriveBeki2List(BitSetDict[2]);
                Bit2ListDict[3] = DeriveBeki2List(BitSetDict[3]);

                // 移動元にコップが無い場合
                if (Bit2ListDict[pFromPos].Count == 0) return;

                // 移動先のコップのほうが大きい場合
                if (Bit2ListDict[pToPos].Count > 0) {
                    int FromCup = Bit2ListDict[pFromPos].Max();
                    int ToCup = Bit2ListDict[pToPos].Max();
                    if (FromCup < ToCup) return;
                }

                BitSetDict[pFromPos] -= Bit2ListDict[pFromPos].Max();
                BitSetDict[pToPos] += Bit2ListDict[pFromPos].Max();

                WillEnqueue.BitSet1 = BitSetDict[1];
                WillEnqueue.BitSet2 = BitSetDict[2];
                WillEnqueue.BitSet3 = BitSetDict[3];
                WillEnqueue.Level = Dequeued.Level + 1;

                long Hash = GetHash(WillEnqueue);
                if (VisitedSet.Add(Hash)) {
                    Que.Enqueue(WillEnqueue);
                }
            };

            EnqueueAct(1, 2);
            EnqueueAct(2, 1);

            EnqueueAct(2, 3);
            EnqueueAct(3, 2);
        }
        Console.WriteLine(-1);
    }

    struct JyoutaiDef
    {
        internal int BitSet1;
        internal int BitSet2;
        internal int BitSet3;
        internal int Level;
    }

    // BitSetを引数として2べきのListを昇順で返す
    static List<int> DeriveBeki2List(int pVal)
    {
        var Beki2List = new List<int>();
        int Beki2 = 1;
        while (Beki2 <= pVal) {
            if ((Beki2 & pVal) > 0) {
                Beki2List.Add(Beki2);
            }
            Beki2 *= 2;
        }
        return Beki2List;
    }

    static long GetHash(JyoutaiDef pJyoutai)
    {
        long Hash = 0;
        Hash += pJyoutai.BitSet1;
        Hash *= 10000000000;
        Hash += pJyoutai.BitSet2;
        Hash *= 100000;
        Hash += pJyoutai.BitSet3;
        return Hash;
    }
}

解説

トレイごとのコップの状態を
BitSetとして持ってBFSしてます。