本题属于状态DP的题目
使用二进制数字枚举每一种可能出现的状态。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=12;
const int M=1<<N;
ll f[N][M];
bool st[M];//这个状态是否合理,检查的是每一个状态的值
int n,m;
int main()
{
while(cin>>n>>m,n||m)
{
//预处理,先检查每一列的各种状态是否是合法的
//总共有2的n次方种状态
for(int i=0;i<1<<n;i++)
{
st[i]=true;
int cnt=0;//统计连续0的个数是否为奇数
for(int j=0;j<n;j++)
{
if(i>>j&1)//当遇到1的时候,判断之前的0的个数是否为奇数个
{
//遇到1了
if(cnt&1)
{
st[i]=false;//这一列已经是不可用的了
break;
}
}
else cnt++;//没有遇到1则0的数目递增
//处理高位的0
//比如总共有四行的时候,状态为0100,后面是偶数个了但是第一行还是奇数个并不对
}
if(cnt&1) st[i]=false;
}
//状态计算
memset(f,0,sizeof(f));
f[0][0]=1;//第一列全竖着放
for(int i=1;i<=m;i++)//从第1列到第m列进行检查
{
for(int j=0;j< 1<<n;j++)
{
for(int k=0;k< 1<<n;k++)
{
//第i列的状态是从第j列转移而来的
//要满足两个条件:两列可以转移,第i列满足存放条件
if((j&k)==0&&st[j|k]!=false)
{
f[i][j]+=f[i-1][k];
}
}
}
}
cout<<f[m][0]<<endl;//第m列全竖放
}
return 0;
}