数据范围这么小,难度又这么大,一般就是状态压缩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=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
}int f[][]={};
int s[];int ans;
int main(){
int n=read(),m=read();
for(int i=;i<=n;++i)
for(int j=;j<=m;++j){
int x=read();
s[i]=(s[i]<<)+x;
}
for(int i=;i<=n;++i)
for(int j=;j<=Max;++j){
if(((j|s[i])!=s[i])||(j&(j<<))) continue;
for(int k=;k<=Max;++k){
if(((k|s[i-])!=s[i-])||(k&(k<<))||(k&j)) continue;
f[i][j]=(f[i][j]+f[i-][k])%mod;
}
}
for(int i=;i<=Max;++i)
ans=(ans+f[n][i])%mod;
printf("%d",ans);
return ;
}