将方格的摆放分成两种：
1.水平摆放：此时所占的两个格子都记为1。
2.竖直摆放：此时底下那个格子记为1，上面那个记为0。
这样的话，每行都会有一个状态表示。
定义：dp[i][s]表示考虑已经填到第i行，这一行状态为s的方法数
转移：dp[i][s] = dp[i][s]+dp[i-1][s'] (s'为上一行的状态，当第i行和第i-1行能够满足条件时，进行转移)
先预处理出所有满足条件的第一行，然后从第二行开始转移。
最后答案为dp[n][(1<<m)-1].
当n<m时交换n和m可减小1<<m，即减少状态数。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
#define ll long long
using namespace std;
#define N 2100 ll dp[][N];
int n,m; int FirstLine(int state)
{
int i=;
while(i<m)
{
if(state & (<<i)) //第i列为1,第i+1列也存在且必须为1
{
if(i < m-)
{
if(state & (<<(i+))) //第i+1列为1
i += ;
else
return ;
}
else
return ;
}
else
i++;
}
return ;
} int Can(int ka,int kb) //ka:这一行，kb:上一行
{
int i = ;
while(i<m)
{
if(ka & (<<i)) //这一行i列为1
{
if(kb & (<<i)) //如果上一行i列为1，则为两个水平块
{
if(i < m- && (ka & (<<(i+))) && (kb & (<<(i+))))
i += ;
else
return ;
}
else //上一行为0,竖着放的
i++;
}
else //这一行i列为0,上一行i列必须填充
{
if(kb & (<<i))
i++;
else
return ;
}
}
return ;
} int main()
{
int i,j,sa;
int state1,state2;
while(scanf("%d%d",&n,&m)!=EOF)
{
if((n*m)%)
{
puts("");
continue;
}
memset(dp,,sizeof(dp));
if(n < m)
swap(n,m);
int MAX = (<<m)-;
for(sa=;sa<=MAX;sa++)
{
if(FirstLine(sa)) //此状态可以作为第一行的状态
dp[][sa] = ;
}
for(i=;i<n;i++) //行递增
{
for(state1=;state1<=MAX;state1++)
{
for(state2=;state2<=MAX;state2++)
{
if(Can(state1,state2))
dp[i][state1] += dp[i-][state2];
}
}
}
printf("%lld\n",dp[n-][MAX]);
}
return ;
}