ABC361-D Go Stone Puzzle

問題へのリンク

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("6");
            WillReturn.Add("BWBWBW");
            WillReturn.Add("WWWBBB");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            WillReturn.Add("BBBBBB");
            WillReturn.Add("WWWWWW");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("14");
            WillReturn.Add("BBBWBWWWBBWWBW");
            WillReturn.Add("WBWWBBWWWBWBBB");
            //7
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static char[] mGoalArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        string StaStr = InputList[1];
        mGoalArr = InputList[2].ToCharArray();

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.Level = 0;

        var BanList = new List<char>();
        for (int I = 0; I <= StaStr.Length - 1; I++) {
            BanList.Add(StaStr[I]);
        }
        BanList.Add('.');
        BanList.Add('.');

        WillEnqueue.BanArr = BanList.ToArray();
        Que.Enqueue(WillEnqueue);

        int UB = BanList.Count - 1;

        var VisitedSet = new HashSet<long>();
        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

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

            int SpaceInd1 = -1;
            int SpaceInd2 = -1;
            for (int I = 0; I <= UB; I++) {
                if (Dequeued.BanArr[I] == '.') {
                    if (SpaceInd1 == -1) {
                        SpaceInd1 = I;
                    }
                    else {
                        SpaceInd2 = I;
                    }
                }
            }

            Action<int, int> EnqueueAct = (pFrom1, pFrom2) =>
            {
                char[] NewBanArr = (char[])Dequeued.BanArr.Clone();
                NewBanArr[SpaceInd1] = Dequeued.BanArr[pFrom1];
                NewBanArr[SpaceInd2] = Dequeued.BanArr[pFrom2];
                NewBanArr[pFrom1] = '.';
                NewBanArr[pFrom2] = '.';

                long Hash = GetHash(NewBanArr);
                if (VisitedSet.Add(Hash)) {
                    WillEnqueue.Level = Dequeued.Level + 1;
                    WillEnqueue.BanArr = NewBanArr;
                    Que.Enqueue(WillEnqueue);
                }
            };

            for (int I = 0; I <= UB - 1; I++) {
                if (Dequeued.BanArr[I] != '.' && Dequeued.BanArr[I + 1] != '.') {
                    EnqueueAct(I, I + 1);
                }
            }
        }
        Console.WriteLine(-1);
    }

    // クリア判定
    static bool IsClear(char[] pBanArr)
    {
        for (int I = 0; I <= mGoalArr.GetUpperBound(0); I++) {
            if (pBanArr[I] != mGoalArr[I]) return false;
        }
        return true;
    }

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

    // 盤面を3進数のハッシュ値に変換
    static long GetHash(char[] pBanArr)
    {
        long Hash = 0;
        foreach (char EachChar in pBanArr) {
            Hash *= 3;
            if (EachChar == 'B') {
                Hash += 1;
            }
            if (EachChar == 'W') {
                Hash += 2;
            }
        }
        return Hash;
    }
}

解説

BFSで解いてます。