Description
举行计算机科学家盛宴的大厅的地板为M×N (1<=M<=9, 1<=N<=9)的矩形。现在必须要铺上硬木地板砖。可以使用的地板砖形状有两种：
1) 2×1的矩形砖
2) 2×2中去掉一个1×1的角形砖你需要计算用这些砖铺满地板共有多少种不同的方案。
注意：必须盖满，地板砖数量足够多，不能存在同时被多个板砖覆盖的部分。
Input
包含M和N。
Output
输出方案总数，如果不可能那么输出0 。
Sample Input
2 3
Sample Output
5
状压DP，搜索求现在状态能达到的所以状态
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define N (1<<11)+3
#define ll long long
ll f[][N];
struct node
{
int to,next;
}e[<<];
int head[N],cnt;
void add(int x,int y)
{
e[cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt++;
}
int n,m;
void dfs(int s1,int s2,int b1,int b2,int step)
{
if(step==m)
{
if(!b1&&!b2)
{
add(s1,s2);
}
return ;
}
dfs(s1|(b1<<step),s2|((-b2)<<step),,,step+);
if(!b1 && !b2)
{
dfs(s1|(<<step),s2,,,step+);
dfs(s1|(<<step),s2,,,step+);
dfs(s1|(<<step),s2,,,step+);
}
if(!b1)
{
dfs(s1|(<<step),s2|((-b2)<<step),,,step+);
dfs(s1|(<<step),s2|((-b2)<<step),,,step+);
}
if(!b2)
{
dfs(s1|(b1<<step),s2,,,step+);
}
}
int main()
{
memset(head,-,sizeof(head));
scanf("%d%d",&n,&m);
dfs(,,,,);
f[][(<<m)-]=;
for(int i=;i<n;i++)
{
for(int S=;S<(<<m);S++)
{
if(f[i][S])
{
for(int k=head[S];k!=-;k=e[k].next)
{
f[i+][e[k].to]+=f[i][S];
}
}
}
}
printf("%lld\n",f[n][(<<m)-]);
return ;
}