AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
术
,
2021-03-06 16:38:04
,
所有人可见
,
阅读 271
#include <iostream>
#include <string.h>
using namespace std;
//先放横着的
//fij j存状态,
int n,m;
const int N=12,M=1<<N;
long long f[N][M];
bool st[M];
int main()
{
while(cin>>n>>m&&!(n==0&&m==0))
{
//预处理 单列是否满足必须连续偶数个要求
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%2==1)
{
st[i]=false;
break;
}
else
cnt=0;
}
else
cnt++;
}
//判断列末尾
if(cnt%2==1)
st[i]=false;
}
//cout<<st[0]<<endl;
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];
}
}
cout<<f[m][0]<<endl;;
}
//cout << "Hello world!" << endl;
return 0;
}