位运算一定要加括号！！！
我因为这个调了40分钟
嗯？01网格图，再看看数据范围，$n,m≤12$，嗯，状压没跑了
$F[i]$表示第$i$行的状态
$f[i][j]$表示前$i$行状态为$j$的合法方案数
$g[i]$表示状态是否合法
左右都是0的状态才合法，当且仅当$i<<1$和$i>>1$都为0的时候合法
当$j==j&F[i]$时，即在肥沃的土地上可以种草时满足题意
且当$j&k==0$时，即上一行与这一行的这个格子没有公共边时，满足题意
code
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define ll long long 5 //const int maxn=5e4+10; 6 const int mod=1e9; 7 inline int read(){ 8 int f=1,x=0;char s=getchar(); 9 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 10 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 11 return f*x; 12 } 13 int n,m,a[15][15],f[15][(1<<15)+10]; 14 int F[15],g[(1<<15)+10],ans; 15 int main(){ 16 m=read();n=read(); 17 for(int i=1;i<=m;i++) 18 for(int j=1;j<=n;j++){ 19 a[i][j]=read(); 20 F[i]=(F[i]<<1)+a[i][j]; 21 } 22 for(int i=0;i<(1<<n);i++){ 23 g[i]=(!(i&(i<<1))&&(!(i&(i>>1)))); 24 } 25 f[0][0]=1; 26 for(int i=1;i<=m;i++) 27 for(int j=0;j<(1<<n);j++){ 28 if(g[j]&&(F[i]&j)==j){ 29 for(int k=0;k<(1<<n);k++){ 30 if((k&j)==0){ 31 f[i][j]=(f[i][j]+f[i-1][k])%mod; 32 // cout<<f[i][j]<<" "; 33 } 34 } 35 } 36 } 37 for(int i=0;i<(1<<n);i++){ 38 ans+=f[m][i];ans%=mod; 39 // cout<<f[m][i]<<" "; 40 } 41 printf("%d",ans); 42 return 0; 43 } 44 } 45 signed main(){ 46 gengyf::main(); 47 return 0; 48 }