写了一个多小时才给它写出来...（呜呜呜
首先，因为一块砖占两个格，所以总格数是单数的话就怎么都铺不满。直接输出 (0) 即可。
然后考虑状压 dp 。设 (f[i][j]) 表示前 (i) 行都放满且对第 (i+1) 行影响为 (j) 时的方案总数。
设数组 (f1[j],f2[j]) 表示第 (j) 种情况由状态 (f1[j]) 可以转移到 (f2[j]) 的状态。
则状态转移方程为 f[i][f2[j]]+=f[i-1][f1[j]]; 。
最后再考虑怎么预处理。可以分三种情况讨论：
-
如果上一行对当前格子的影响为 (1) 也就是上面已经有砖块了，那么这里就不放，且对下一行的影响为 (0) 。
-
如果上一行对当前格子的影响为 (0) ，那么我们可以选择竖着放一块，对下一行的影响为 (1) 。
-
对于上种情况也可以横着放一个，对下一行没有影响，但记得 (p) 要一次性加上 (2) 。（刚才写的时候这里踩坑了qaq)
#include<bits/stdc++.h>
using namespace std;
int f[12][1<<12],f1[20001],f2[20001];
int m,n,cnt;
void dfs(int p,int st,int ed)
{
if(p==m)
{
cnt++;
f1[cnt]=st;f2[cnt]=ed;
return;
}
if(p>m) return;
dfs(p+1,(st<<1)+1,(ed<<1));
dfs(p+1,(st<<1),(ed<<1)+1);
dfs(p+2,(st<<2),(ed<<2));
return;
}
int main()
{
while(scanf("%d%d",&n,&m))
{
if(n==0&&m==0) break;
cnt=0;
memset(f,0,sizeof(f));
dfs(0,0,0);
f[0][0]=1;
if(m*n%2)
{
cout<<"0"<<endl;
continue;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=cnt;j++)
{
f[i][f2[j]]+=f[i-1][f1[j]];
}
}
cout<<f[n][0]<<endl;
}
return 0;
}