ABC224-D 8 Puzzle on Graph

問題へのリンク

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

    static int mM;

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

    static int[] mBanArr;

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

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

        SplitAct(InputList[0]);
        mM = int.Parse(InputList[0]);

        foreach (string EachStr in InputList.Skip(1).Take(mM)) {
            SplitAct(EachStr);
            int FromNode = wkArr[0] - 1;
            int ToNode = wkArr[1] - 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[] PArr = InputList.Last().Split(' ').Select(pX => int.Parse(pX)).ToArray();

        mBanArr = new int[9];
        for (int I = 0; I <= PArr.GetUpperBound(0); I++) {
            mBanArr[PArr[I] - 1] = I + 1;
        }

        ExecBFS();
    }

    struct JyoutaiDef
    {
        internal int[] BanArr;
        internal int Level;
    }

    static void ExecBFS()
    {
        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.BanArr = mBanArr;
        WillEnqueue.Level = 0;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<long>();
        VisitedSet.Add(GetHash(mBanArr));

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();
            if (IsClear(Dequeued.BanArr)) {
                Console.WriteLine(Dequeued.Level);
                return;
            }

            int Ind0 = Array.IndexOf(Dequeued.BanArr, 0);
            if (mToNodeListDict.ContainsKey(Ind0)) {
                foreach (int EachFromNode in mToNodeListDict[Ind0]) {
                    WillEnqueue.BanArr = (int[])Dequeued.BanArr.Clone();
                    int FromNum = Dequeued.BanArr[EachFromNode];
                    WillEnqueue.BanArr[Ind0] = FromNum;
                    WillEnqueue.BanArr[EachFromNode] = 0;
                    WillEnqueue.Level = Dequeued.Level + 1;
                    long Hash = GetHash(WillEnqueue.BanArr);
                    if (VisitedSet.Add(Hash)) {
                        Que.Enqueue(WillEnqueue);
                    }
                }
            }
        }
        Console.WriteLine(-1);
    }

    // クリア判定
    static bool IsClear(int[] pArr)
    {
        for (int I = 0; I <= 7; I++) {
            if (pArr[I] != I + 1) return false;
        }
        return true;
    }

    // ハッシュ値を求める
    static long GetHash(int[] pArr)
    {
        long WillReturn = 0;
        foreach (int EachInt in pArr) {
            WillReturn += EachInt;
            WillReturn *= 10;
        }
        return WillReturn;
    }
}

解説

ナイーブに幅優先探索してます。