传送门
题意简述：给一个有障碍的网格图，问用若干个不相交的回路覆盖所有非障碍格子的方案数。
思路：轮廓线dpdpdp的模板题。
同样是讨论插头的情况，只不过没有前一道题复杂，不懂的看代码吧。
代码：
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define ri register int
using namespace std;
using namespace tr1;
typedef long long ll;
int n,m,zx=-1,zy=-1,cur;
bool mp[15][15];
char s[15];
ll ans=0;
const int mod=1e6+7;
struct Statement{
int tot,idx[mod],sta[mod];
ll num[mod];
inline void clear(){memset(idx,-1,sizeof(idx)),tot=0;}
inline void insert(int stat,ll nume){
int pos=stat%mod;
if(!pos)++pos;
while(~idx[pos]&&sta[idx[pos]]!=stat)pos=pos==mod-1?1:pos+1;
if(~idx[pos])num[idx[pos]]+=nume;
else sta[idx[pos]=++tot]=stat,num[tot]=nume;
}
}f[2];
inline int getbit(int x,int p){return (x>>(p-1))&1;}
inline void update(int&x,int p,int v){x^=(v^getbit(x,p))<<(p-1);}
inline void solve(){
f[cur=0].clear(),f[cur].insert(0,1);
for(ri i=1;i<=n;++i){
for(ri j=1;j<=m;++j){
cur^=1,f[cur].clear();
for(ri tt=1;tt<=f[cur^1].tot;++tt){
int stat=f[cur^1].sta[tt],p=getbit(stat,j),q=getbit(stat,j+1);
ll dpnum=f[cur^1].num[tt];
if(!mp[i][j]){if(!(p+q))f[cur].insert(stat,dpnum);continue;}
if(!(p+q)){
if(mp[i][j+1]&&mp[i+1][j])update(stat,j,1),update(stat,j+1,1),f[cur].insert(stat,dpnum);
continue;
}
if(!p){
if(mp[i][j+1])f[cur].insert(stat,dpnum);
if(mp[i+1][j])update(stat,j,1),update(stat,j+1,0),f[cur].insert(stat,dpnum);
continue;
}
if(!q){
if(mp[i+1][j])f[cur].insert(stat,dpnum);
if(mp[i][j+1])update(stat,j,0),update(stat,j+1,1),f[cur].insert(stat,dpnum);
continue;
}
update(stat,j,0),update(stat,j+1,0),f[cur].insert(stat,dpnum);
if(i==zx&&j==zy)ans+=dpnum;
}
}
for(ri j=1;j<=f[cur].tot;++j)f[cur].sta[j]<<=1;
}
}
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int main(){
for(ri up=read(),tt=1;tt<=up;++tt){
n=read(),m=read(),zx=zy=-1,memset(mp,0,sizeof(mp));
for(ri i=1;i<=n;++i)for(ri j=1;j<=m;++j)if(mp[i][j]=read())zx=i,zy=j;
if(zx==-1)puts("0");
else ans=0,solve(),cout<<"Case "<<tt<<": There are "<<ans<<" ways to eat the trees.\n";
}
return 0;
}