用 2x1 榻榻米垫填充 HxW 房间有多少种方法？

Question

问题

我想看看用榻榻米垫（1x2 瓷砖）平铺 HxW 网格的方法？
但是榻榻米的填充物有一个特殊的规定，就是不能与榻榻米的边框交叉
这个问题我写过代码，速度很慢
如果H=20 and W=20，它可能得到1秒。我想计算更多的大案例。
有什么高效的算法吗？

例子

我有一个 H=3、W=4 和 H=4、W=4 的例子。
如果H=3 and W=4，有4种方式。
如果H=4 and W=4，有2种方式

我当前的代码 (C++)

#include <cstdio>
#include <vector>
 
using namespace std;
 
int H, W;
 
inline bool hantei(vector<vector<int> > tatami)
{
    bool ok = true;
 
    for (int k = 0; k < H - 1; k++)
    {
        for (int l = 0; l < W - 1; l++)
        {
            int c1 = tatami[k][l];
            int c2 = tatami[k][l + 1];
            int c3 = tatami[k + 1][l];
            int c4 = tatami[k + 1][l + 1];
 
            bool ok2 = !(c1 > 0 && c2 > 0 && c3 > 0 && c4 > 0 && c1 != c2 && c1 != c3 && c1 != c4 && c2 != c3 && c2 != c4 && c3 != c4);
 
            ok = ok && ok2;
        }
    }
 
    return ok;
}
 
inline int dfs(int count_, vector<vector<int> > tatami)
{
    if ((count_ - 1) * 2 == H * W)
    {
        return 1;
    }
 
    int sum = 0;
 
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if (!tatami[i][j])
            {
                if (H - i - 1)
                {
                    if (!tatami[i + 1][j])
                    {
                        vector<vector<int> > tatami2(tatami.begin(), tatami.end());
 
                        tatami2[i][j] = count_; tatami2[i + 1][j] = count_;
 
                        if (!hantei(tatami2)) { return 0; }
 
                        sum += dfs(count_ + 1, tatami2);
                    }
                }
 
                if (W - j - 1)
                {
                    if (!tatami[i][j + 1])
                    {
                        vector<vector<int> > tatami2(tatami.begin(), tatami.end());
 
                        tatami2[i][j] = count_; tatami2[i][j + 1] = count_;
 
                        if (!hantei(tatami2)) { return 0; }
 
                        sum += dfs(count_ + 1, tatami2);
                    }
                }
 
                return sum;
            }
        }
    }
 
    return 0;
}
 
int main()
{
    while (true)
    {
        scanf("%d", &H);
        scanf("%d", &W);
 
        if (H == 0 && W == 0) { break; }
 
        if (H % 2 == 1 && W % 2 == 1)
        {
            printf("0\n");
        }
        else if (H == 1 || W == 1)
        {
            printf("1\n");
        }
        else if (H == W)
        {
            printf("2\n");
        }
        else
        {
            vector<vector<int> > start(H, vector<int>(W, 0));
 
            printf("%d\n", dfs(1, start));
        }
    }
 
    return 0;
}

编辑：此代码正在搜索比必要更多的节点（递归次数）。如果H,W <= 20，答案不会超过1000。

感谢您的阅读。

Answer 1

这个问题已由 Dean Hickerson 调查（参见 http://oeis.org/A068920/a068920.txt）。您可以在链接位置找到证明和递归算法。