Q61 同じ大きさに分割

C#のソース

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

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

    //DFSでの分割用
    struct JyoutaiDefDFS
    {
        internal char[,] BanArr;
        internal int Level;
    }

    //UnionFindで島のチェック用
    struct JyoutaiDefUnionFind
    {
        internal int CurrX;
        internal int CurrY;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDefDFS>();
        JyoutaiDefDFS WillPush;
        WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
        for (int X = 0; X <= UB_X; X++)
            for (int Y = 0; Y <= UB_Y; Y++)
                WillPush.BanArr[X, Y] = 'W';

        WillPush.BanArr[0, 0] = 'B';
        WillPush.Level = 1;
        stk.Push(WillPush);

        var PushedBanSet = new HashSet<string>();

        int AnswerCnt = 0;
        while (stk.Count > 0) {
            JyoutaiDefDFS Popped = stk.Pop();

            //クリア判定
            if (Popped.Level == (UB_X + 1) * (UB_Y + 1) / 2) {
                AnswerCnt++;
                Console.WriteLine("解{0}を発見", AnswerCnt);
                PrintBan(Popped.BanArr);
                continue;
            }

            Action<int, int> PushSyori = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB_X < pNewX) return;
                if (pNewY < 0 || UB_Y < pNewY) return;

                if (Popped.BanArr[pNewX, pNewY] == 'B') return;
                WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                WillPush.BanArr[pNewX, pNewY] = 'B';
                WillPush.Level = Popped.Level + 1;

                if (WillEdakiri(WillPush.BanArr)) return;

                string BanStr = BanToStr(WillPush.BanArr);
                if (PushedBanSet.Add(BanStr) == false) return;

                stk.Push(WillPush);
            };

            for (int X = 0; X <= UB_X; X++) {
                for (int Y = 0; Y <= UB_Y; Y++) {
                    if (Popped.BanArr[X, Y] != 'B') continue;
                    PushSyori(X, Y - 1); PushSyori(X, Y + 1);
                    PushSyori(X - 1, Y); PushSyori(X + 1, Y);
                }
            }
        }
    }

    //枝切り判定
    static bool WillEdakiri(char[,] pBanArr)
    {
        var stk = new Stack<JyoutaiDefUnionFind>();
        JyoutaiDefUnionFind WillPush;

        var VisitedSet = new HashSet<string>();

        bool WillBreak = false;
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                if (pBanArr[X, Y] == 'W') {
                    WillPush.CurrX = X;
                    WillPush.CurrY = Y;
                    stk.Push(WillPush);
                    VisitedSet.Add(string.Format("{0},{1}", X, Y));
                    WillBreak = true;
                    break;
                }
            }
            if (WillBreak) break;
        }

        while (stk.Count > 0) {
            JyoutaiDefUnionFind Popped = stk.Pop();

            Action<int, int> PushSyori = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB_X < pNewX) return;
                if (pNewY < 0 || UB_Y < pNewY) return;

                if (pBanArr[pNewX, pNewY] == 'B') return;
                string wkStr = string.Format("{0},{1}", pNewX, pNewY);
                if (VisitedSet.Add(wkStr) == false) return;

                WillPush.CurrX = pNewX;
                WillPush.CurrY = pNewY;
                stk.Push(WillPush);
            };

            PushSyori(Popped.CurrX, Popped.CurrY - 1);
            PushSyori(Popped.CurrX, Popped.CurrY + 1);
            PushSyori(Popped.CurrX - 1, Popped.CurrY);
            PushSyori(Popped.CurrX + 1, Popped.CurrY);
        }

        //全ての白マスに訪問不可なら枝切り
        return VisitedSet.Count < pBanArr.Cast<char>().Count(X => X == 'W');
    }

    //盤面をStr型に変換
    static string BanToStr(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]);
            }
        }
        return sb.ToString();
    }

    //盤面を出力
    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());
    }
}

実行結果

省略
解243を発見
BWWWW
BWBWW
BWBBW
BBBBW

解244を発見
BWWWW
BWBBW
BWBWW
BBBBW

解245を発見
BWWWW
BWBBW
BWBBW
BBBWW

解説

左上の隅を固定で黒として、深さ優先探索で配置を列挙してます。