【HDU 1693】Eat the Trees

题目传送门: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;
}