题目描述
在n* m的方格中，用1* 2和2*1两种块把方格铺满有多少种铺法
输入输出格式
输入格式：
两个整数，n，m。
输出格式：
一个整数，表示方案数
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int n,m;
ll f[20][10010];
void dfs(int x,int y,int now,int nxt)
{
if(x==n)
{
f[y+1][nxt]+=f[y][now];
return;
}
if((now&(1<<x))==0)dfs(x+1,y,now,nxt|(1<<x));
if(x+1<n&&((now&(1<<x))==0)&&((now&(1<<(x+1)))==0))dfs(x+2,y,now,nxt);
if((now&(1<<x))>0)dfs(x+1,y,now,nxt);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n+m==0)break;
if((n*m)&1){printf("0\n");continue;}
if(m<n)swap(n,m);
memset(f,0,sizeof(f));
f[1][0]=1;
for(int i=1;i<=m;++i)
for(int j=0;j<(1<<n);++j)
if(f[i][j]>0)dfs(0,i,j,0);
printf("%lld\n",f[m+1][0]);
}
return 0;
}