ABC244-D Swap Hats

問題へのリンク

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("R G B");
            WillReturn.Add("R G B");
            //Yes
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static string mSArr;
    static string mTArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mSArr = InputList[0].Replace(" ", "");
        mTArr = InputList[1].Replace(" ", "");

        bool Result = ExecDFS();
        Console.WriteLine(Result ? "Yes" : "No");
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal string RGBStr;
    }

    static bool ExecDFS()
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.RGBStr = mSArr;

        Stk.Push(WillPush);

        var VisitedSet = new HashSet<string>();

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            // クリア判定
            if (Popped.RGBStr == mTArr) {
                if (Popped.Level % 2 == 0) {
                    return true;
                }
            }

            Action<int, int> PushAct = (pInd1, pInd2) =>
            {
                char[] CharArr = Popped.RGBStr.ToCharArray();
                char wkChar = CharArr[pInd1];
                CharArr[pInd1] = CharArr[pInd2];
                CharArr[pInd2] = wkChar;
                WillPush.RGBStr = new string(CharArr);

                WillPush.Level = (Popped.Level + 1) % 2;

                string Hash = GetHash(WillPush);
                if (VisitedSet.Add(Hash)) {
                    Stk.Push(WillPush);
                }
            };
            PushAct(0, 1);
            PushAct(0, 2);
            PushAct(1, 2);
        }
        return false;
    }

    static string GetHash(JyoutaiDef pJyoutai)
    {
        return string.Format("{0},{1}", pJyoutai.Level, pJyoutai.RGBStr);
    }
}

解説

DFSしつつ、
レベルの偶奇と色の並びでハッシュ値を作って再訪防止してます。

偶数レベルでゴールに到達できれば、解ありと判定してます。