トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

Q70 青白歌合戦


C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int UB_X;
    const int UB_Y = 4 - 1;

    static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();

    static void Main()
    {
        UB_X = 4 - 1; Solve();
        UB_X = 6 - 1; Solve();
    }

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

    static void Solve()
    {
        var Queue = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnque;

        var VisitedSet = new HashSet<uint>();

        List<char[,]> InitList;
        if (UB_X == 4 - 1) InitList = DeriveInitList_4_4();
        else InitList = DeriveInitList_6_4();

        foreach (char[,] EachInitList in InitList) {
            WillEnque.BanArr = EachInitList;
            WillEnque.Level = 0;
            Queue.Enqueue(WillEnque);
            VisitedSet.Add(BanToUntSet(EachInitList).First());
        }

        int AnswerLevel = 0;
        List<char[,]> AnswerBanArrList = new List<char[,]>();
        while (Queue.Count > 0) {
            JyoutaiDef Dequeued = Queue.Dequeue();

            if (AnswerLevel < Dequeued.Level) {
                AnswerBanArrList.Clear();
                AnswerLevel = Dequeued.Level;
                Console.WriteLine("移動回数{0,2}の解候補を発見。経過時間={1}",
                    AnswerLevel, sw.Elapsed);
            }
            AnswerBanArrList.Add(Dequeued.BanArr);

            //青に隣接した白の座標の、ペアのListを返す
            List<RinsetuInfoDef> RinsetuInfoList = DeriveRinsetuInfoList(Dequeued.BanArr);

            foreach (RinsetuInfoDef EachRinsetuInfo in RinsetuInfoList) {
                WillEnque.BanArr = (char[,])Dequeued.BanArr.Clone();
                WillEnque.BanArr[EachRinsetuInfo.BX, EachRinsetuInfo.BY] = 'W';
                WillEnque.BanArr[EachRinsetuInfo.WX, EachRinsetuInfo.WY] = 'B';

                //メモ化探索
                HashSet<uint> wkHashSet = BanToUntSet(WillEnque.BanArr);
                if (VisitedSet.Overlaps(wkHashSet)) continue;
                VisitedSet.Add(wkHashSet.First());

                WillEnque.Level = Dequeued.Level + 1;

                Queue.Enqueue(WillEnque);
            }
        }
        HashSet<uint> AnswerSet = new HashSet<uint>();
        AnswerBanArrList.ForEach(X => AnswerSet.UnionWith(BanToUntSet(X)));

        Console.WriteLine("解は、移動回数{0}で{1,2}通り。経過時間={2}",
            AnswerLevel, AnswerSet.Count, sw.Elapsed);
        Console.WriteLine("解の例");
        PrintBan(AnswerBanArrList[0]);
    }

    //最初の盤面のListを返す(4*4の盤面用)
    static List<char[,]> DeriveInitList_4_4()
    {
        var WillReturn = new List<char[,]>();

        WillReturn.Add(ConvCharArr(new string[]{"BBWW",
                                                "BBWW",
                                                "BBWW",
                                                "BBWW"}));
        return WillReturn;
    }

    //最初の盤面のListを返す(6*4の盤面用)
    static List<char[,]> DeriveInitList_6_4()
    {
        var WillReturn = new List<char[,]>();

        WillReturn.Add(ConvCharArr(new string[]{"BBBWWW",
                                                "BBBWWW",
                                                "BBBWWW",
                                                "BBBWWW"}));

        WillReturn.Add(ConvCharArr(new string[]{"BBBBBB",
                                                "BBBBBB",
                                                "WWWWWW",
                                                "WWWWWW"}));

        return WillReturn;
    }

    //String型の配列を、Char型の2次元配列に変換
    static char[,] ConvCharArr(string[] pStrArr)
    {
        char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];
        for (int Y = 0; Y <= pStrArr.GetUpperBound(0); Y++) {
            for (int X = 0; X <= pStrArr[Y].Length - 1; X++) {
                WillReturn[X, Y] = pStrArr[Y][X];
            }
        }
        return WillReturn;
    }

    struct RinsetuInfoDef
    {
        internal int BX;
        internal int BY;
        internal int WX;
        internal int WY;
    }

    //青に隣接した白の座標の、ペアのListを返す
    static List<RinsetuInfoDef> DeriveRinsetuInfoList(char[,] pBanArr)
    {
        var WillReturn = new List<RinsetuInfoDef>();

        //座標を引数として、Wかを返す
        Func<int, int, bool> wkFunc = (pX, pY) =>
        {
            if (pX < 0 || UB_X < pX) return false;
            if (pY < 0 || UB_Y < pY) return false;

            return pBanArr[pX, pY] == 'W';
        };

        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (pBanArr[LoopX, LoopY] != 'B') continue;

                if (wkFunc(LoopX, LoopY - 1)) {
                    WillReturn.Add(
                        new RinsetuInfoDef() { BX = LoopX, BY = LoopY, WX = LoopX, WY = LoopY - 1 });
                }
                if (wkFunc(LoopX, LoopY + 1)) {
                    WillReturn.Add(
                        new RinsetuInfoDef() { BX = LoopX, BY = LoopY, WX = LoopX, WY = LoopY + 1 });
                }
                if (wkFunc(LoopX - 1, LoopY)) {
                    WillReturn.Add(
                        new RinsetuInfoDef() { BX = LoopX, BY = LoopY, WX = LoopX - 1, WY = LoopY });
                }
                if (wkFunc(LoopX + 1, LoopY)) {
                    WillReturn.Add(
                        new RinsetuInfoDef() { BX = LoopX, BY = LoopY, WX = LoopX + 1, WY = LoopY });
                }
            }
        }
        return WillReturn;
    }

    //盤面をUInt型のSetに変換
    static HashSet<uint> BanToUntSet(char[,] pBanArr)
    {
        var WillReturn = new HashSet<uint>();

        var sbList = new List<System.Text.StringBuilder>();

        for (int I = 1; I <= (UB_X == UB_Y ? 8 : 4); I++)
            sbList.Add(new System.Text.StringBuilder());

        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                Func<char, char> wkFunc = pChar => pChar == 'B' ? '0' : '1';

                sbList[0].Append(wkFunc(pBanArr[X, Y]));
                sbList[1].Append(wkFunc(pBanArr[X, UB_Y - Y]));
                sbList[2].Append(wkFunc(pBanArr[UB_X - X, Y]));
                sbList[3].Append(wkFunc(pBanArr[UB_X - X, UB_Y - Y]));
                if (UB_X == UB_Y) {
                    sbList[4].Append(wkFunc(pBanArr[Y, X]));
                    sbList[5].Append(wkFunc(pBanArr[UB_Y - Y, X]));
                    sbList[6].Append(wkFunc(pBanArr[Y, UB_X - X]));
                    sbList[7].Append(wkFunc(pBanArr[UB_Y - Y, UB_X - X]));
                }
            }
        }
        sbList.ForEach(X => WillReturn.Add(Convert.ToUInt32(X.ToString(), 2)));
        return WillReturn;
    }

    //盤面を出力
    static void PrintBan(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}


実行結果

省略
移動回数10の解候補を発見。経過時間=00:00:00.2582674
解は、移動回数10で64通り。経過時間=00:00:00.2615463
解の例
BBWB
BWWB
WWWW
BBWB

移動回数 1の解候補を発見。経過時間=00:00:00.2637234
移動回数 2の解候補を発見。経過時間=00:00:00.2646224
移動回数 3の解候補を発見。経過時間=00:00:00.2676736
移動回数 4の解候補を発見。経過時間=00:00:00.2785806
移動回数 5の解候補を発見。経過時間=00:00:00.3249091
移動回数 6の解候補を発見。経過時間=00:00:00.4491311
移動回数 7の解候補を発見。経過時間=00:00:00.8075878
移動回数 8の解候補を発見。経過時間=00:00:01.6484938
移動回数 9の解候補を発見。経過時間=00:00:03.5248449
移動回数10の解候補を発見。経過時間=00:00:07.2977886
移動回数11の解候補を発見。経過時間=00:00:14.0524248
移動回数12の解候補を発見。経過時間=00:00:25.1072295
移動回数13の解候補を発見。経過時間=00:00:42.3790152
移動回数14の解候補を発見。経過時間=00:01:06.4787971
移動回数15の解候補を発見。経過時間=00:01:34.9050734
移動回数16の解候補を発見。経過時間=00:01:56.7399803
移動回数17の解候補を発見。経過時間=00:02:03.8539730
移動回数18の解候補を発見。経過時間=00:02:05.0332396
移動回数19の解候補を発見。経過時間=00:02:05.1789101
移動回数20の解候補を発見。経過時間=00:02:05.1909591
解は、移動回数20で 4通り。経過時間=00:02:05.1960657
解の例
WBBBBW
WWBBWW
WWBBWW
WBBBBW


解説

回転も含めた同一ノードへの再訪を防止しながら、幅優先探索し、
最後に、回転も含めた盤面の数を求めてます。