题目描述
求把 N×M 的棋盘分割成若干个 1×2 的的长方形,有多少种方案。
例如当 N=2,M=4 时,共有 5 种方案。当 N=2,M=3 时,共有 3 种方案。
样例
输入样例:
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
输出样例:
1
0
1
2
3
5
144
51205
f[i][j]表示第i列的上一列伸出的状态为j
当一个N*M的方格被横放的矩形放好后,竖放的只有一种放法
#include<iostream>
#include<cstring>
using namespace std;
const int N=12,M=1<<N;
bool st[M];
long long f[N][M];
int main()
{
int n,m;
while(cin>>n>>m,n||m)
{
for(int i=0;i<1<<n;i++)//预处理j|k
{
int cnt=0;
st[i]=true;
for(int j=0;j<n;j++)
{
if((i>>j&1)==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;//当第0列伸出状态为0时候,竖放的格子只有一种放法
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];//当j&k=0表示横放的格子没有重叠
//st[j|k]表示j和k之间没有连续的奇数个格子
cout<<f[m][0]<<endl;
}
return 0;
}