蒙德里安的梦想
题目链接
解题思路
考虑横线块(1 * 2)的不同放法,剩下的位置只能放置纵向块(2 * 1)
我们可以用二维数组来存储 f[i][j] 来存储每一个状态,i 表示当前是第 i 列,j 是一个十进制数,若存在横向块位于 i , i + 1 ,那么对应的十进制位为1 ,否则为 0 。如下图
我们需要使横向块和纵向块分布满整个矩阵则需要满足条件
- 相邻两列的块不会重合,即对于 f[i, j] 和 f[i - 1, k],j & k == 0
- 存在于同一列的最近两块之间相邻格子应为偶数,即对于 f[i, j] 和 f[i - 1, k] ,j | k 不存在奇数个连续的0
C ++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 12, M = 1 << N;
int n, m;
long long f[N][M];
bool st[M];
int main()
{
while (scanf("%d%d", &n, &m), n || m)
{
for (int i = 0; i < 1 << n; i ++ )
{
st[i] = true;
int cnt = 0; //记录两个块之间的格子数量(纵向)
for (int j = 0; j < n; j ++ )
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] = 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];
printf("%lld\n", f[m][0]);
}
return 0;
}