题意： 给出一个n*m大小的01矩阵，在其中画线连成封闭图形，其中对每一个值为1的方格，线要恰好穿入穿出共两次，对每一个值为0的方格，所画线不能经过。
参考资料： 《基于连通性状态压缩的动态规划问题》 ——陈丹琦 2008年国家集训队论文
递推过程中，按照 遍历行->遍历行上每一格->遍历 “轮廓线跨过该格时所有可能的状态变化” 的顺序
这样复杂度是 O(n*m*2m+1) （m+1是因为轮廓线上有m个单元是与列数对应的，另有一单独的竖线单元）
问题关键点在于解决 “轮廓线跨过该格时所有可能的状态变化”
首先是由第i行到第i+1行的递推关系。显然，第i+1行上，轮廓线未跨过任何方格，与在第i行，轮廓线跨过了所有方格，这两者轮廓线的形态是相同的，不过，前者的状态state1应表示为后者的状态state2<<1，在代码中，计数关系通过 for(int k=0;k<M;k++) dp[i][0][k<<1]=dp[i-1][m][k]; 来实现。
然后是在同一行上跨过某一格时的递推关系。不考虑方格值为0，这道题里面共有四种情况，对于具体某一格而言，即 00->11,01->10,10->01,11->00。对于方格值为0的情况，显然只能是00->00。
后继状态总计数=sigma合法的前驱状态。
具体可以借助代码来理解
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn=13; int n,m; int mp[maxn][maxn]; LL dp[maxn][maxn][1<<maxn]; LL solve() { int M=1<<(m+1); //轮廓线上状态总数 dp[0][m][0]=1; for(int i=1;i<=n;i++) //遍历行 { for(int k=0;k<M;k++) dp[i][0][k<<1]=dp[i-1][m][k]; for(int j=1;j<=m;j++) //j用来指示轮廓线中小竖线的位置 { int state1=(1<<j),state2=(1<<(j-1)); for(int k=0;k<M;k++) { if(mp[i][j]) { if((k&state1)==0&&(k&state2)==0) dp[i][j][k]=dp[i][j-1][k+state1+state2]; else if((k&state1)!=0&&(k&state2)!=0) dp[i][j][k]=dp[i][j-1][k-state1-state2]; else if((k&state1)==0&&(k&state2)!=0) { dp[i][j][k]+=dp[i][j-1][k-state2+state1]; dp[i][j][k]+=dp[i][j-1][k]; } else { dp[i][j][k]+=dp[i][j-1][k-state1+state2]; dp[i][j][k]+=dp[i][j-1][k]; } } else if((k&state1)==0&&(k&state2)==0) dp[i][j][k]=dp[i][j-1][k]; } } } return dp[n][m][0]; } int main() { int T,kase=0; scanf("%d",&T); while(T--) { memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]); printf("Case %d: There are %lld ways to eat the trees. ",++kase,solve()); } }