自我认为写的还算通俗易懂
关于捅出来:由于定义的是横着摆放的小矩形,上一列有会导致将下一列的该位置占用掉
参考代码:
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 12, M = 1 << N;
int n, m;
// 转态压缩DP
// 时间复杂度:11 * 1 << 11 * 1 << 11 = 10 * 2000 * 2000 = 4e7
// 结论:如果将横着的小矩形摆放完毕(横着摆的矩形要满足两个条件,才能使得合法且竖着的空的位置可以摆放竖着的小矩形以及两个横着的不会冲突),则剩下的矩形只能竖着摆放,且摆放方式唯一
// 1. 对于当前列i来说,如果第i列的当前位置被第i - 1列横着摆的桶了出来而占用,并且第i - 1列的当前位置被第i - 2列横着摆的桶了出来而占用,会发现,第i - 1列的当前位置是两个1 * 1小矩形的覆盖,不符合合法情况
// 2. 要想保证横着摆放完,剩下用来摆放竖着的矩形的位置可以合法摆放,得使得每一列的连续的空的位置为偶数才可以合法摆放
// 对于两种情况用代码表示如下:j 表示当前列的转态, k 表示上一列的状态
// 1. j & k == 0 表示没有冲突
// 2. st[j | k] == true 表示当前转态下没有奇数连续的情况,为合法情况
// f[i][j]:表示第i列(0 ~ n - 1)的j状态(二进制表示范围为1 << n,二进制的第k位为1表示上一列横着摆的的小矩形捅了出来,则会造成当前列该位置被占用),值表示当前状态的总方案数
// 结果很大,用long long来存储
long long f[N][M];
// 表示当前状态下是否有奇数个连续空位 没有为true 有为false
bool st[M];
int main(){
// 简单的逗号表达式 0 0 时退出
while(cin >> n >> m, n || m){
// 预处理st数组
for(int i = 0; i < 1 << n; i++){
int cnt = 0;
st[i] = true;
for(int j = 0; j < n; j++){
// 处理两个1之间的0的个数
if(i >> j & 1){
if(cnt & 1) st[i] = false;
cnt = 0;
}else cnt ++;
}
// 处理最后一次统计
if(cnt & 1) st[i] = false;
}
memset(f, 0, sizeof f);
// 初始化:f[0][0]表示第0列没有被捅出来的情况下的方案数,很明显,第一列只能竖着放,方案数唯一,所以为1
f[0][0] = 1;
// 列
for(int i = 1; i <= m; i++)
// 当前列转态
for(int j = 0; j < 1 << n; j++)
// 上一列的转态
for(int k = 0; k < 1 << n; k++)
// 两个条件合法才是合法方案
if((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];
// 最终答案:应该为m - 1列,但是为了满足最后一列不能捅出来,可以使得最后一列的下一列转态为0即可
cout << f[m][0] << endl;
}
return 0;
}