【题目分析】
吃树。
直接插头DP，算是一道真正的入门题目。
0/1表示有没有插头
【代码】
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define u64 unsigned long long
#define F(i,j,k) for (int i=j;i<=k;++i)
int n,m,t,a[12][12],kas;
u64 dp[2][1<<12];
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
F(i,0,n-1) F(j,0,m-1) scanf("%d",&a[i][j]);
int now=1,pre=0;
memset(dp[now],0,sizeof dp[now]);
dp[now][0]=1;
F(i,0,n-1)
F(j,0,m-1)
{
if (a[i][j]){
now^=1;pre^=1;
memset(dp[now],0,sizeof dp[now]);
F(s,0,(1<<(m+1))-1) if(dp[pre][s])
{
if ((s&(1<<j))&&(s&(1<<(j+1)))) dp[now][s^(1<<j)^(1<<(j+1))]+=dp[pre][s];
if ((s&(1<<j))&&(!(s&(1<<(j+1))))) dp[now][s]+=dp[pre][s],dp[now][s^(1<<j)^(1<<(j+1))]+=dp[pre][s];
if ((!(s&(1<<j)))&&(s&(1<<(j+1)))) dp[now][s]+=dp[pre][s],dp[now][s^(1<<j)^(1<<(j+1))]+=dp[pre][s];
if ((!(s&(1<<j)))&&(!(s&(1<<(j+1))))) dp[now][s^(1<<j)^(1<<(j+1))]+=dp[pre][s];
}
}
else
{
now^=1;pre^=1;
memset(dp[now],0,sizeof dp[now]);
F(s,0,(1<<(m+1))-1) if (dp[pre][s]) if ((!(s&(1<<j)))&&(!(s&(1<<(j+1))))) dp[now][s]+=dp[pre][s];
}
if (j==m-1)
{
now^=1;pre^=1;
memset(dp[now],0,sizeof dp[now]);
F(s,0,(1<<(m+1))-1) if (!(s&(1<<m)))
dp[now][(s<<1)&((1<<(m+1))-1)]=dp[pre][s];
}
}
printf("Case %d: There are %llu ways to eat the trees.
",++kas,dp[now][0]);
}
}