题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1693
#include<iostream> #include<cstdio> #include<cstring> #define LL long long using namespace std; const int MAXN = 5000; LL f[12][12][MAXN]; int MX,n,m,mat[12][12]; int main(){ int TT; cin>>TT; for (int T=1;T<=TT;T++) { scanf("%d%d",&m,&n); MX =1<<n+1; for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) scanf("%d",&mat[i][j]),memset(f[i][j],0,sizeof(f[i][j])); if (mat[1][1]) f[1][1][3] = 1; else f[1][1][0] = 1; for (int j=1;j<=m;j++) { for (int i=1;i<n;i++) { for (int k=0;k<MX;k++) if (f[i][j][k]) { bool up=k&(1<<i+1), left=k&(1<<i); if (mat[i+1][j]) { if (up && left) f[i+1][j][k^(1<<i)^(1<<i+1)] += f[i][j][k]; else if (up || left) { f[i+1][j][k] += f[i][j][k]; f[i+1][j][k^(1<<i+1)^(1<<i)] += f[i][j][k]; } else { f[i+1][j][k^(1<<i+1)^(1<<i)] += f[i][j][k]; } } else { if (!up && !left) f[i+1][j][k] += f[i][j][k]; } } } for (int k=0;k<MX;k++) if (f[n][j][k] && (k&(1<<n)) == 0) { int up = k & 1; if (mat[1][j+1]) { if (up) { f[1][j+1][((k^1)<<1)^1] += f[n][j][k]; f[1][j+1][((k^1)<<1)^2] += f[n][j][k]; } else { f[1][j+1][(k<<1)^3] += f[n][j][k]; } } else { if (!up) f[1][j+1][k<<1] += f[n][j][k]; else continue; } } } printf("Case %d: There are %I64d ways to eat the trees.\n",T,f[n][m][0]); } return 0; }