トップページに戻る    次の増井さんの書籍の問題へ    前の増井さんの書籍の問題へ

Q32 畳を敷きつめろ


C#のソース

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

class Program
{
    //ピースごとの配置候補
    static Dictionary<char, bool[,]> HaitiKouhoArrDict = new Dictionary<char, bool[,]>();

    static char[] TatamiArr = { '-', '|' };

    static void Main()
    {
        foreach (char EachTatami in TatamiArr) {
            HaitiKouhoArrDict[EachTatami] = DeriveHaitiKouhoArr(EachTatami);
        }

        Solve(3, 4);
        Solve(4, 7);
        Solve(5, 6);
    }

    static int UB_X;
    static int UB_Y;

    struct JyoutaiDef
    {
        internal char[,] BanArr;
        internal int CurrX;
        internal int CurrY;
        internal int TatamiCnt;
    }

    static void Solve(int pTate, int pYoko)
    {
        Console.WriteLine(new string('■', 15));
        Console.WriteLine("縦{0}*横{1}での解を調査します。", pTate, pYoko);
        Console.WriteLine();

        UB_X = pYoko - 1;
        UB_Y = pTate - 1;

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef 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] = ' ';

        WillPush.CurrX = WillPush.CurrY = 0;
        WillPush.TatamiCnt = 0;
        stk.Push(WillPush);

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

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

            //X座標の繰上げ処理
            if (Popped.CurrX > UB_X) {
                Popped.CurrX = 0;
                Popped.CurrY++;
            }

            //最終行を超えた場合
            if (Popped.CurrY > UB_Y) continue;

            //10進数をchar型に変換
            Func<int, char> DecToStr = (pInt) =>
            {
                if (pInt < 10) return (char)((int)'1' + pInt - 1);
                return (char)((int)'A' + pInt - 10);
            };

            foreach (char EachTatami in TatamiArr) {
                bool[,] HaitiKouhoArr = HaitiKouhoArrDict[EachTatami];

                //マス目にピースを埋めれない場合
                if (CanFillPiece(HaitiKouhoArr, Popped.CurrX, Popped.CurrY, Popped.BanArr) == false)
                    continue;

                //ピースを配置する経路のPush処理
                WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                WillPush.CurrX = Popped.CurrX + 1;
                WillPush.CurrY = Popped.CurrY;
                WillPush.TatamiCnt = Popped.TatamiCnt + 1;

                for (int X = 0; X <= HaitiKouhoArr.GetUpperBound(0); X++) {
                    for (int Y = 0; Y <= HaitiKouhoArr.GetUpperBound(1); Y++) {
                        if (HaitiKouhoArr[X, Y] == false) continue;
                        WillPush.BanArr[Popped.CurrX + X, Popped.CurrY + Y] =
                            DecToStr(WillPush.TatamiCnt);
                    }
                }
                if (HasJyuuji(Popped.CurrX, Popped.CurrY, WillPush.BanArr) == false)
                    stk.Push(WillPush);
            }

            //現在のマス目が空白でない場合は、畳を配置しない経路のPush
            if (Popped.BanArr[Popped.CurrX, Popped.CurrY] != ' ') {
                WillPush.BanArr = Popped.BanArr;
                WillPush.CurrX = Popped.CurrX + 1;
                WillPush.CurrY = Popped.CurrY;
                WillPush.TatamiCnt = Popped.TatamiCnt;
                stk.Push(WillPush);
            }
        }
    }

    //十字が存在するかを判定
    static bool HasJyuuji(int pTargetX, int pTargetY, char[,] pBanArr)
    {
        //敷き詰めるマス、左上、左、上で4枚の畳なら十字が存在している
        if (pTargetX - 1 < 0) return false;
        if (pTargetY - 1 < 0) return false;

        if (pBanArr[pTargetX - 1, pTargetY - 1] == pBanArr[pTargetX - 1, pTargetY]) return false;
        if (pBanArr[pTargetX - 1, pTargetY - 1] == pBanArr[pTargetX, pTargetY - 1]) return false;
        if (pBanArr[pTargetX - 1, pTargetY - 1] == pBanArr[pTargetX, pTargetY]) return false;
        return true;
    }

    //ピース名を引数として、回転させた配置のListを返す
    static bool[,] DeriveHaitiKouhoArr(char pTatami)
    {
        bool[,] wkArr = null;

        //■■
        if (pTatami == '-') {
            wkArr = new bool[2, 1];
            wkArr[0, 0] = wkArr[1, 0] = true;
        }

        //■
        //■
        if (pTatami == '|') {
            wkArr = new bool[1, 2];
            wkArr[0, 0] = true;
            wkArr[0, 1] = true;
        }
        return wkArr;
    }

    //マス目にピースを埋めれるか
    static bool CanFillPiece(bool[,] pPieceMap, int pTargetX, int pTargetY, char[,] pBanArr)
    {
        for (int X = 0; X <= pPieceMap.GetUpperBound(0); X++) {
            if (pTargetX + X > UB_X) return false;
            for (int Y = 0; Y <= pPieceMap.GetUpperBound(1); Y++) {
                if (pTargetY + Y > UB_Y) return false;
                if (pPieceMap[X, Y] && pBanArr[pTargetX + X, pTargetY + Y] != ' ')
                    return false;
            }
        }
        return true;
    }

    //解を出力
    static void PrintAnswer(char[,] pBanArr)
    {
        //'-'と'|'を設定
        while (pBanArr.Cast<char>().All(X => X == '-' || X == '|') == false) {
            for (int X = 0; X <= UB_X; X++) {
                for (int Y = 0; Y <= UB_Y; Y++) {
                    char CurrChar = pBanArr[X, Y];
                    if (CurrChar == '-' || CurrChar == '|')
                        continue;

                    //横方向に同じ数字があったら'-'
                    bool SameYoko = false;
                    for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                        if (LoopX == X) continue;
                        if (pBanArr[LoopX, Y] == CurrChar) {
                            pBanArr[LoopX, Y] = '-';
                            SameYoko = true;
                            break;
                        }
                    }
                    pBanArr[X, Y] = (SameYoko ? '-' : '|');
                }
            }
        }

        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());
    }
}


実行結果

省略
■■■■■■■■■■■■■■■
縦4*横7での解を調査します。

解1を発見
|--|--|
|||||||
|||||||
|--|--|

解2を発見
--|----
||||--|
||||--|
--|----

解3を発見
----|--
|--||||
|--||||
----|--

■■■■■■■■■■■■■■■
縦5*横6での解を調査します。

解1を発見
|----|
||--||
||--||
|----|
------

解2を発見
------
|----|
||--||
||--||
|----|


解説

深さ優先探索で敷き詰めつつ、十字が存在したら枝切りしてます。