题意:m*n的格子里放1*3的矩形,问有多少种放法。
分析:状态压缩dp,每个格子有三种状态,dp[i][j]表示到第i层状态为j的方法数。
#include <iostream>
#include <memory.h>
#include <stdio.h>
using namespace std;
#define LL long long
LL dp[31][20000],n,m,row,zt;
LL num[10],pp[10];
// 状态 0----横放或者竖放的第三个格子 对下层没有影响
// 1----竖放的中间那个格子 对下一层有影响
// 2----竖放的第一个格子 对下两层有影响
void dfs(LL pos,LL status)
{
if(pos==n)
{
dp[row+1][status]+=dp[row][zt];
return;
}
if(num[pos]==0) // 上层为0 这层可以横放或者成2
{
if(pos+2<n&&num[pos+1]==0&&num[pos+2]==0) dfs(pos+3,status); // 横放
dfs(pos+1,status+2*pp[pos]);
}
else if(num[pos]==1) // 上层为1 这层为0
{
dfs(pos+1,status);
}
else // 上层为2 这层为1
{
dfs(pos+1,status+pp[pos]);
}
}
void change()
{
LL now=zt,k=-1;
memset(num,0,sizeof(num));
if(now==0) return;
while(now)
{
num[++k]=now%3;
now/=3;
}
}
int main()
{
LL i,nmax;
pp[0]=1;
for(i=1;i<=9;i++) pp[i]=pp[i-1]*3;
while(scanf("%lld%lld",&n,&m)&&(m||n))
{
if((m*n)%3!=0) {printf("0\n"); continue;}
nmax=pp[n]; // 状态总数
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(row=0;row<=m-1;row++)
{
for(zt=0;zt<nmax;zt++)
{
if(dp[row][zt])
{
change();
dfs(0,0);
}
}
}
printf("%lld\n",dp[m][0]);
}
return 0;
}