AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
AC_
,
2021-01-29 17:55:03
,
所有人可见
,
阅读 323
#include<iostream>
#include<cstring>
using namespace std;
const int M = 12, N = 1 << M;
int m, n;
long long f[M][N];
bool st[N];
int main()
{
while (1) {
scanf("%d %d", &m, &n);
if (m == 0 && n == 0) break;
memset(f, 0, sizeof f);
for (int i = 0; i < 1 << m; i ++) {
int cnt = 0;
st[i] = true;
for (int j = 0; j < m; j ++) {
if ((i >> j) & 1) {
if (cnt & 1) {
st[i] = false;
break;
} else {
cnt = 0;
}
} else {
cnt ++;
}
}
if (cnt & 1) st[i] = false;
}
f[0][0] = 1;
for (int i = 1; i <= n; i ++)
for (int j = 0; j < (1 << m); j ++)
for (int k = 0; k < (1 << m); k ++)
if ((j & k) == 0 && st[j | k]) f[i][j] += f[i - 1][k];
cout << f[n][0] << endl;
}
return 0;
}