n乘m的矩阵，1表示这块区域可以放牛，0,表示不能，而且不能在相邻的(包括上下相邻)两个区域放牛，问有多少种放牛的方法，全部不放也是一种方法。
对于每块可以放牛的区域，有放或者不放两种选择，状压DP，dp[i][j]表示第 i 行以state[j]这种状态的时候和方法取值。
具体的参考http://www.tuicool.com/articles/JVzMVj
写的很详细。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; int dp[][],cas=,n,m;
int state[],cur[];
int mod=1e9; void init()
{
int q=(<<m);
for (int i= ; i<q ; i++)
{
if (i&(i<<)) continue;
state[++cas]=i;
}
} bool judge(int x,int y)
{
if (x&cur[y]) return false;//不符合
return true;
} int main()
{
scanf("%d%d",&n,&m);
init();
for (int i= ; i<=n ; i++){
cur[i]=;int x;
for (int j= ; j<=m ; j++){
scanf("%d",&x);
if (x==) cur[i]+=(<<(m-j));
}
}
for (int i= ; i<=cas ; i++)
if (judge(state[i],))
dp[][i]=;
for (int i= ; i<=n ; i++){
for (int j= ; j<=cas ; j++){
if (judge(state[j],i)==false) continue;
for (int k= ; k<=cas ; k++){
if (judge(state[k],i-)==false) continue;
if (state[k]&state[j]) continue;
dp[i][j]=(dp[i][j]+dp[i-][k])%mod;
}
}
}
int maxn=;
for (int i= ; i<=cas ; i++)
maxn=(maxn+dp[n][i])%mod;
printf("%d\n",maxn);
return ;
}