数据范围这么小，难度又这么大，一般就是状态压缩DP了。
对输入进行处理，二进制表示每一行的草地状况。如111表示这一行草地肥沃，压缩成7.
所以f[i][j]表示第i行状态为j时的方案数
状态j指的是一个二进制集合，有牛在吃草的位置是1，不再吃草的位置是0
f[i][j]=Sum(f[i-1][k])
限制：(1) j必须是草地状况的子集。很好理解，如果有牛在贫瘠草地上吃草……会被投诉到动物保护协会的
(2) j 的相邻两个位置不能都是1。 代码表示为!(j&(j<<1)
(3) k 的上述两个限制。
(4) k和j没有交集。这样可以保证没有相邻两个位置是1。
代码如下
#include<cstdio> #include<cctype> #include<cstdlib> #include<iostream> #define mod 100000000 #define Max ((1<<m)-1) using namespace std; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } int f[20][200000]={1}; int s[20]; int ans; int main(){ int n=read(),m=read(); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ int x=read(); s[i]=(s[i]<<1)+x; } for(int i=1;i<=n;++i) for(int j=0;j<=Max;++j){ if(((j|s[i])!=s[i])||(j&(j<<1))) continue; for(int k=0;k<=Max;++k){ if(((k|s[i-1])!=s[i-1])||(k&(k<<1))||(k&j)) continue; f[i][j]=(f[i][j]+f[i-1][k])%mod; } } for(int i=0;i<=Max;++i) ans=(ans+f[n][i])%mod; printf("%d",ans); return 0; }