ARC132-B Shift and Reverse

問題へのリンク

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");
            WillReturn.Add("1 3 2");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("2 1");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("2 3 4 5 6 7 8 9 10 1");
            //3
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("12");
            WillReturn.Add("1 2 3 4 5 6 7 8 9 10 11 12");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int[] mPArr;
    static int UB;

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal bool IsReverse; // リバース中か？
        internal int Level;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        mPArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        UB = mPArr.GetUpperBound(0);

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrInd = 0;
        WillEnqueue.IsReverse = false;
        WillEnqueue.Level = 0;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<int>();

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

            // クリア判定
            if (IsClear(Dequeued)) {
                Console.WriteLine(Dequeued.Level);
                return;
            }

            Action<JyoutaiDef> EnqueueAct = (pJyoutai) =>
            {
                IndFix(ref pJyoutai.CurrInd);
                int Hash = GetHash(pJyoutai);
                if (VisitedSet.Add(Hash)) {
                    Que.Enqueue(pJyoutai);
                }
            };

            // リバースする場合
            if (Dequeued.IsReverse == false) {
                WillEnqueue.CurrInd = Dequeued.CurrInd - 1;
                WillEnqueue.IsReverse = (Dequeued.IsReverse == false);
                WillEnqueue.Level = Dequeued.Level + 1;
                EnqueueAct(WillEnqueue);
            }
            else {
                WillEnqueue.CurrInd = Dequeued.CurrInd + 1;
                WillEnqueue.IsReverse = (Dequeued.IsReverse == false);
                WillEnqueue.Level = Dequeued.Level + 1;
                EnqueueAct(WillEnqueue);
            }

            // シフトする場合
            if (Dequeued.IsReverse == false) {
                WillEnqueue.CurrInd = Dequeued.CurrInd + 1;
                WillEnqueue.IsReverse = Dequeued.IsReverse;
                WillEnqueue.Level = Dequeued.Level + 1;
                EnqueueAct(WillEnqueue);
            }
            else {
                WillEnqueue.CurrInd = Dequeued.CurrInd - 1;
                WillEnqueue.IsReverse = Dequeued.IsReverse;
                WillEnqueue.Level = Dequeued.Level + 1;
                EnqueueAct(WillEnqueue);
            }
        }
    }

    // インデックスの調整
    static void IndFix(ref int pInd)
    {
        if (pInd == -1) pInd = UB;
        if (pInd == UB + 1) pInd = 0;
    }

    // クリア判定
    static bool IsClear(JyoutaiDef pJyoutai)
    {
        int Ind1 = pJyoutai.CurrInd;
        if (mPArr[Ind1] != 1) return false;

        int Ind2 = Ind1;
        if (pJyoutai.IsReverse) {
            Ind2--;
        }
        else {
            Ind2++;
        }

        IndFix(ref Ind2);
        if (mPArr[Ind2] != 2) return false;

        return true;
    }

    // ハッシュ値を求める
    static int GetHash(JyoutaiDef pJyoutai)
    {
        return pJyoutai.CurrInd * 2 + (pJyoutai.IsReverse ? 1 : 0);
    }
}

解説

数珠の状態でBFSしてます。