题意:在n*m的方格里铺1*2的骨牌，有多少种可能，首先可以排除一些特殊情况，n*m是奇数，就是0
n或m是1就是1（已经排除n*m的情况）。然后就和我之前写的hdu1992的插头dp一样
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
long long dp[15][4444];
int m;
void dfs(int s,int ss,int x,int n) {
///s上一行对这一行的影响，（即当前行的状态），ss当前行构造的对下一行的影响
///x正在处理第几列，n正在处理第几行 该矩阵是4列n行的
if(x>m-1) { ///全部处理完了
dp[n+1][ss]+=dp[n][s];
return;
}
if(s&(1<<x)) { ///如果上一行已经占有这一行的这一格了直接跳过
dfs(s,ss,x+1,n);
return;
}
dfs(s,ss|(1<<x),x+1,n); ///竖着放已经确定该行没被占用。
if(x<=m-2&&!(s&(1<<(x+1)))) { ///横着放，先确认下一行有没有被占用
dfs(s,ss,x+2,n);///横着放并不会影响下一行 。
}
return;
}
int main()
{
int n;
while(scanf("%d%d",&n,&m)&&(n+m)!=0) {
if(m==0||n==0||(m*n)&1) {
printf("0\n");
continue;
}
if(m==1||n==1) {
if(n==1) {
printf("%d\n",m&1?0:1);
continue;
}
if(m==1) {
printf("%d\n",n&1?0:1);
continue;
}
}
if(n<m) swap(n,m);
memset(dp,0,sizeof dp);
dp[0][0]=1;
for(int i=0;i<n;i++)
for(int j=0;j<(1<<m);j++) {
if(dp[i][j]) {
dfs(j,0,0,i);
}
}
printf("%lld\n",dp[n][0]);
}
return 0;
}