ABC289-E Swap Places

問題へのリンク

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

    static int mN;
    static int mM;
    static int[] mCArr;

    // 隣接リスト
    static Dictionary<int, List<int>> mToNodeListDict = new Dictionary<int, List<int>>();

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

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

        var sb = new System.Text.StringBuilder();
        int CurrInd = 1;
        while (CurrInd <= InputList.Count - 1) {
            SplitAct(InputList[CurrInd]);
            mN = wkArr[0];
            mM = wkArr[1];
            SplitAct(InputList[CurrInd + 1]);
            mCArr = (int[])wkArr.Clone();

            mToNodeListDict.Clear();
            for (int I = CurrInd + 2; I <= CurrInd + mM + 1; I++) {
                SplitAct(InputList[I]);
                int FromNode = wkArr[0];
                int ToNode = wkArr[1];

                if (mToNodeListDict.ContainsKey(FromNode) == false) {
                    mToNodeListDict[FromNode] = new List<int>();
                }
                if (mToNodeListDict.ContainsKey(ToNode) == false) {
                    mToNodeListDict[ToNode] = new List<int>();
                }
                mToNodeListDict[FromNode].Add(ToNode);
                mToNodeListDict[ToNode].Add(FromNode);
            }
            int Result = Solve();
            sb.Append(Result);
            sb.AppendLine();
            CurrInd += 1 + mM + 1;
        }
        Console.Write(sb.ToString());
    }

    struct JyoutaiDef
    {
        internal int CurrNode1;
        internal int CurrNode2;
        internal int Level;
    }

    static int Solve()
    {
        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode1 = 1;
        WillEnqueue.CurrNode2 = mN;
        WillEnqueue.Level = 0;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<int>();
        VisitedSet.Add(GetHash(WillEnqueue));

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();
            if (Dequeued.CurrNode1 == mN && Dequeued.CurrNode2 == 1) {
                return Dequeued.Level;
            }

            if (mToNodeListDict.ContainsKey(Dequeued.CurrNode1) == false) {
                continue;
            }
            if (mToNodeListDict.ContainsKey(Dequeued.CurrNode2) == false) {
                continue;
            }

            foreach (int EachToNode1 in mToNodeListDict[Dequeued.CurrNode1]) {
                foreach (int EachToNode2 in mToNodeListDict[Dequeued.CurrNode2]) {
                    int Color1 = mCArr[EachToNode1 - 1];
                    int Color2 = mCArr[EachToNode2 - 1];
                    if (Color1 == Color2) continue;
                    WillEnqueue.CurrNode1 = EachToNode1;
                    WillEnqueue.CurrNode2 = EachToNode2;
                    WillEnqueue.Level = Dequeued.Level + 1;
                    if (VisitedSet.Add(GetHash(WillEnqueue))) {
                        Que.Enqueue(WillEnqueue);
                    }
                }
            }
        }
        return -1;
    }

    static int GetHash(JyoutaiDef pJyoutai)
    {
        return pJyoutai.CurrNode1 * 10000 + pJyoutai.CurrNode2;
    }
}

解説

高橋君と青木君の頂点のペアで再訪防止し、BFSしてます。