题意：给出一个n行m列的草地，1表示肥沃，0表示贫瘠，现在要把一些牛放在肥沃的草地上，但是要求所有牛不能相邻，问你有多少种放法。
分析：假如我们知道第 i-1 行的所有的可以放的情况，那么对于第 i 行的可以放的一种情况，我们只要判断它和 i - 1 行的所有情况的能不能满足题目的所有牛不相邻，如果有种中满足，那么对于 i 行的这一中情况有 x 中放法。 但是我们又发现，状态是一种放法，不是我们平常dp的简单的状态，所以要用状态压缩！
dp[i][j]表示第i行状态为j的个数。
dp[i][j] = sum{dp[i-1][k]};
第i行可以由上一行的合法的状态推导来。
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1000000007
#define mod 100000000
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN = ;
int n,m;
int mp[MAXN];
int dp[MAXN][(<<MAXN)];
int q[<<MAXN],cnt;
int main()
{
while(~scanf("%d%d",&n,&m)){
int x;
cnt = ;
memset(mp,,sizeof(mp));
for(int i = ; i <= n; i++){
for(int j = ; j <= m; j++){
scanf("%d",&x);
if(x == ){
mp[i] |= (<<(j-));//mp[i]存合法的状态 x=1的时候，用0存，0的时候用1存。
}
}
}
memset(dp,,sizeof(dp));//dp表示第i行状态为j时合法的个数
for(int i = ; i < ( << m); i++){//在一行中把没有相邻的合法的状态记录下来
if(!(i & (i << ))){
q[cnt++] = i;
}
}
for(int i = ; i < cnt; i++){//对第一行初始化。由于mp存第i行合法的状态，又0用1 1用0表示，所以mp[1]&q[i]==0
//表示和合法的状态
if(!(mp[] & q[i])){
dp[][i] = ;
}
}
for(int i = ; i <= n; i++){//从第2行开始枚举
for(int j = ; j < cnt; j++){//枚举状态
if(mp[i] & q[j]){//不合法的状态
continue;
}
for(int k = ; k < cnt; k++){
if((mp[i-] & q[k]) == && (q[j] & q [k]) == ){
dp[i][j] = (dp[i][j] + dp[i-][k])%mod;
}
}
}
}
ll ans = ;
for(int i = ; i < cnt; i++){
ans =(ans + dp[n][i]) % mod;
}
cout<<ans<<endl;
}
return ;
}