先坑着，等啥时候会了再来填坑
不得不说思路真的是很妙啊
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #define ll long long 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 inline int read(){ 10 #define num ch-'0' 11 char ch;bool flag=0;int res; 12 while(!isdigit(ch=getc())) 13 (ch=='-')&&(flag=true); 14 for(res=num;isdigit(ch=getc());res=res*10+num); 15 (flag)&&(res=-res); 16 #undef num 17 return res; 18 } 19 const int N=20; 20 int n,m,bin[N],mp[N][N]; 21 ll f[N][N][(1<<12)+5]; 22 void solve(int x,int y){ 23 int plug1=bin[y-1],plug2=bin[y]; 24 if(mp[x][y]){ 25 for(int j=0;j<bin[m+1];++j){ 26 f[x][y][j]+=f[x][y-1][j^plug1^plug2]; 27 if(((j>>(y-1))&1)==((j>>y)&1)) continue; 28 f[x][y][j]+=f[x][y-1][j]; 29 } 30 } 31 else{ 32 for(int j=0;j<bin[m+1];++j){ 33 if(!(j&plug1)&&!(j&plug2)) f[x][y][j]=f[x][y-1][j]; 34 else f[x][y][j]=0; 35 } 36 } 37 } 38 int main(){ 39 // freopen("testdata.in","r",stdin); 40 int T=read(); 41 bin[0]=1;for(int i=1;i<=15;++i) bin[i]=bin[i-1]<<1; 42 for(int t=1;t<=T;++t){ 43 n=read(),m=read(); 44 for(int i=1;i<=n;++i) 45 for(int j=1;j<=m;++j) 46 mp[i][j]=read(); 47 memset(f,0,sizeof(f)); 48 f[1][0][0]=1; 49 for(int i=1;i<=n;++i){ 50 for(int j=1;j<=m;++j) solve(i,j); 51 if(i!=n) for(int j=0;j<bin[m];++j) 52 f[i+1][0][j<<1]=f[i][m][j]; 53 } 54 printf("Case %d: There are %lld ways to eat the trees. ",t,f[n][m][0]); 55 } 56 return 0; 57 }