Problem215 亀裂のない壁

問題

2x1 と 3x1 のレンガ(水平x垂直方向)を使って壁を建てる.
ただし追加条件として, 水平方向に隣接したレンガ間の隙間が上下の層にまたがってはならない.
つまり, 伝播亀裂がないようにする.

例として, 下図の9x3の壁は条件を満たしていない. 赤線が伝播亀裂だからである.



9x3の亀裂のない壁は8通りの建て方がある.
これを W(9,3)=8 と表す.

W(32,10) を計算せよ.

ソース

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

class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        Solve(9, 3);
        Solve(32, 10);
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    static int UB_X;
    static int UB_Y;

    static void Solve(int pW, int pH)
    {
        UB_X = pW - 1;
        UB_Y = pH - 1;

        //レンガの亀裂の配列のListを求める
        List<int[]> KiretuArrList = DeriveKiretuArrList();
        int UB = KiretuArrList.Count - 1;

        //上下に配置可能なレンガの配置IDの配列を求める
        var CanSetArrDict = new Dictionary<int, int[]>();
        for (int I = 0; I <= UB; I++) {
            var CanSetList = new List<int>();
            for (int J = 0; J <= UB; J++) {
                if (CanSetJyouge(KiretuArrList[I], KiretuArrList[J]) == false)
                    continue;
                CanSetList.Add(J);
            }
            CanSetArrDict.Add(I, CanSetList.ToArray());
        }

        //場合の数[現在の配置ID]なDP表
        long[] PrevDP = new long[UB + 1];
        for (int I = 0; I <= UB; I++)
            PrevDP[I] = 1;

        for (int Y = 1; Y <= UB_Y; Y++) {
            long[] CurrDP = new long[UB + 1];

            for (int I = 0; I <= UB; I++) {
                for (int J = 0; J <= UB; J++) {
                    //上下に配置可能なIDかを判定
                    if (Array.BinarySearch(CanSetArrDict[I], J) >= 0)
                        CurrDP[J] += PrevDP[I];
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine("W({0},{1})={2}", pW, pH, PrevDP.Sum());
    }

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal List<int> KiretuList;
    }

    //レンガの亀裂の配列のListを求める
    static List<int[]> DeriveKiretuArrList()
    {
        var WillReturn = new List<int[]>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrInd = 0;
        WillPush.KiretuList = new List<int>();
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            //クリア判定
            if (Popped.CurrInd == UB_X + 1) {
                WillReturn.Add(Popped.KiretuList.ToArray());
            }
            if (Popped.CurrInd > UB_X + 1) continue;

            Action<int> PushSyori = (pNewInd) =>
            {
                WillPush.CurrInd = pNewInd;
                WillPush.KiretuList = new List<int>(Popped.KiretuList);
                WillPush.KiretuList.Add(pNewInd - 1);
                Stk.Push(WillPush);
            };

            PushSyori(Popped.CurrInd + 2); //2マスのレンガ
            PushSyori(Popped.CurrInd + 3); //3マスのレンガ
        }
        return WillReturn;
    }

    //2つの配列を引数として、上下に配置可能かを返す
    static bool CanSetJyouge(int[] pArr1, int[] pArr2)
    {
        foreach (int EachInt in pArr1) {
            //最後は、対象外
            if (EachInt == UB_X) continue;

            if (Array.IndexOf(pArr2, EachInt) >= 0)
                return false;
        }
        return true;
    }
}

実行結果

W(9,3)=8
W(32,10)=806844323190414
経過時間=00:00:06.5017655

解説

上下に配置可能なレンガの配置の組み合わせを列挙してから、
場合の数[現在の配置ID]を更新する動的計画法を使ってます。