题目大意：在 n * m 有障碍棋盘上找若干曼哈顿回路使之遍历所有合法位置，求方案数。
轮廓线动态规划。逐格转移，记状态 f[i, j, k] 为处理至第 (i, j) 格（设 0 ≤ i < n，0 ≤ j < m），前 n 格轮廓线上插头状态为 k 的方案数，记 0 为无插头，1 为有插头，利用二进制状态压缩，则 k 二进制下从低位向高位第 1 位表示当前格前第 1 格右边界是否有插头，第 l + 1 位表示当前格前第 l 格下边界是否有插头的状态，可知 k 最多只需记 m + 1 位即可。对于当前状态 k，转移分为以下五种情况：
当前格为合法位置，且当前格左边界无插头（即 j = 0 或 k and 1 = 0），且当前格上边界无插头（即 i = 0 或 k and 2m = 0），此时必在当前格右边界和下边界间连路径，即状态 f[i, j - 1, k] （或状态 f[i - 1, m - 1, k]） 可以转移到状态 f[i, j, k * 2 xor 3]。
当前格为合法位置，且当前格左边界无插头（即 j = 0 或 k and 1 = 0），且当前格上边界有插头（即 i > 0 且 k and 2m = 1），此时可以在当前格上边界和右边界间连路径，即状态 f[i, j - 1, k] （或状态 f[i - 1, m - 1, k]） 可以转移到状态 f[i, j, k * 2 xor 2m+1 xor 1]，或可以在当前格上边界和下边界间连路径，即状态 f[i, j - 1, k] （或状态 f[i - 1, m - 1, k]） 可以转移到状态 f[i, j, k * 2 xor 2m+1 xor 2]。
当前格为合法位置，且当前格左边界有插头（即 j > 0 且 k and 1 = 1），且当前格上边界无插头（即 i = 0 或 k and 2m = 0），此时可以在当前格左边界和右边界间连路径，即状态 f[i, j - 1, k] 可以转移到状态 f[i, j, k * 2 xor 3]，或可以在当前格左边界和下边界间连路径，即状态 f[i, j - 1, k] 可以转移到状态 f[i, j, k * 2]。
当前格为合法位置，且当前格左边界有插头（即 j > 0 且 k and 1 = 1），且当前格上边界有插头（即 i > 0 且 k and 2m = 1），此时必在当前格左边界和上边界间连路径，即状态 f[i, j - 1, k] 可以转移到状态 f[i, j, k * 2 xor 2m+1 xor 2]。
当前格为不合法位置，此时若当前格左边界无插头（即 j = 0 或 k and 1 = 0），且当前格上边界无插头（即 i = 0 或 k and 2m = 0），则状态 f[i, j - 1, k] （或状态 f[i - 1, m - 1, k]） 可以转移到状态 f[i, j, k * 2]。
设初始状态 f[-1, m - 1, 0] = 1，f[-1, m - 1, 1 .. 2m+1−1 ] = 0，转移相当于方案数求和，则状态 f[n - 1, m - 1, 0] 即为答案。可以采用滚动数组优化，降低空间复杂度和编程复杂度。由于答案过大，故需用到超长整型保存答案。
代码如下：
#include<iostream> #include<stdio.h> using namespace std; long long f[2][4100]; int main() { int cur,m,n,t,val; scanf("%d",&t); for(int l=1;l<=t;l++) { scanf("%d %d",&n,&m); cur=0; for(int i=0;i<1<<m+1;i++) f[0][i]=f[1][i]=0; f[cur][0]=1; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { scanf("%d",&val); if(val>0) { for(int k=0;k<1<<m;k+=2) f[cur^1][k<<1^3]+=f[cur][k],f[cur][k]=0, f[cur^1][k<<1^1]+=f[cur][k^1<<m],f[cur^1][k<<1^2]+=f[cur][k^1<<m],f[cur][k^1<<m]=0; if(j>0) for(int k=0;k<1<<m;k+=2) f[cur^1][k<<1^1]+=f[cur][k^1],f[cur^1][k<<1^2]+=f[cur][k^1],f[cur][k^1]=0, f[cur^1][k<<1]+=f[cur][k^1<<m^1],f[cur][k^1<<m^1]=0; else for(int k=1;k<1<<m+1;k+=2) f[cur][k]=0; } else for(int k=0;k<1<<m;k+=2) f[cur^1][k<<1]+=f[cur][k],f[cur][k]=f[cur][k^1]=f[cur][k^1<<m]=f[cur][k^1<<m^1]=0; cur^=1; } cout<<"Case "<<l<<": There are "<<f[cur][0]<<" ways to eat the trees."<<endl; } return 0; }