c++ - 用2x1的榻榻米垫子可以在HxW房间中填充多少种方式？

Closed. This question needs to be more focused。它当前不接受答案。












想改善这个问题吗？更新问题，使其仅关注editing this post的一个问题。

3年前关闭。



Improve this 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，则有两种方法。



我当前的代码(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
感谢您的阅读。

最佳答案

Dean Hickerson已研究了此问题(请参阅http://oeis.org/A068920/a068920.txt)。您可以在链接的位置找到证明和递归算法。

关于c++ - 用2x1的榻榻米垫子可以在HxW房间中填充多少种方式？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41319522/