蒙德里安矩形填充问题题解

问题描述

我们需要计算用1×2或2×1的小矩形完全填充一个h×w的大矩形的不同方法数。需要考虑所有可能的填充方式，包括对称的填充方式。

解题思路

这个问题可以使用动态规划和状态压缩的方法来解决。关键在于如何表示每一行的填充状态，并通过状态转移来计算所有可能的填充方式。

关键步骤

1. 预处理可行状态：确定哪些状态表示合法的行填充方式（即可以被水平放置的1×2砖块完全覆盖）
2. 动态规划状态转移：计算从上一行状态到当前行状态的转移方式
3. 边界条件处理：初始化第一行的状态

标程

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;

ll dp[12][1<<11];  // dp[i][j]表示第i行状态为j时的填充方法数
bool ok[1<<11];    // 标记哪些状态是合法的
int n, m;

int main() {
    while(~scanf("%d%d",&n,&m) && (n|m)) {
        // 预处理所有可能的行状态
        for(int i=0; i<1<<m; ++i) {
            bool cnt = 0;
            for(int j=0; j<m; ++j) {
                if(i>>j & 1) {  // 如果第j位是1（表示垂直放置的砖块）
                    if(cnt == 1) {  // 如果前面有未配对的0
                        ok[i] = 0;
                        break;
                    }
                    cnt = 0;
                } else {
                    cnt ^= 1;  // 记录连续的0的个数
                }
                if(j == m-1) {
                    ok[i] = (cnt == 0);  // 最后必须所有0都配对
                }
            }
        }

        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;  // 初始状态：第0行全空

        for(int i=1; i<=n; ++i) {  // 处理每一行
            for(int j=0; j<1<<m; ++j) {  // 当前行状态
                dp[i][j] = 0;
                for(int k=0; k<1<<m; ++k) {  // 上一行状态
                    // 状态转移条件：
                    // 1. 两行垂直砖块不重叠(j&k==0)
                    // 2. 合并后的水平砖块填充合法(ok[j|k])
                    if((j&k)==0 && ok[j|k]) {
                        dp[i][j] += dp[i-1][k];
                    }
                }
            }
        }

        printf("%lld\n", dp[n][0]);  // 最终状态：最后一行全空
    }
    return 0;
}

算法分析

1. 状态表示：

   • 使用二进制数表示每一行的填充状态
   • 0表示水平放置的砖块的一部分，1表示垂直放置的砖块

2. 预处理阶段：

   • 检查每个状态是否能被水平砖块完全填充（即所有0必须成对出现）

3. 动态规划转移：

   • 从上一行的状态k转移到当前行状态j
   • 转移条件：垂直砖块不冲突(j&k==0)，且合并后的水平填充合法(ok[j|k])

4. 复杂度分析：

   • 时间复杂度：O(n × 2^m × 2^m) = O(n × 4^m)
   • 空间复杂度：O(n × 2^m)

示例解释

对于输入2×2的情况：

1. 预处理发现合法状态有：00, 11
2. 状态转移：
   • 从第0行空状态可以转移到第1行的00或11状态
   • 从第1行的00状态可以转移到第2行的00或11状态
   • 从第1行的11状态只能转移到第2行的00状态
3. 最终结果为2种填充方式

该算法高效地计算了所有可能的填充方式，适用于题目给定的约束条件（h,w ≤ 11）。