n乘m的矩阵，1表示这块区域可以放牛，0,表示不能，而且不能在相邻的(包括上下相邻)两个区域放牛，问有多少种放牛的方法，全部不放也是一种方法。
对于每块可以放牛的区域，有放或者不放两种选择，状压DP，dp[i][j]表示第 i 行以state[j]这种状态的时候和方法取值。
具体的参考http://www.tuicool.com/articles/JVzMVj
写的很详细。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 int dp[20][600],cas=0,n,m; 8 int state[600],cur[20]; 9 int mod=1e9; 10 11 void init() 12 { 13 int q=(1<<m); 14 for (int i=0 ; i<q ; i++) 15 { 16 if (i&(i<<1)) continue; 17 state[++cas]=i; 18 } 19 } 20 21 bool judge(int x,int y) 22 { 23 if (x&cur[y]) return false;//不符合 24 return true; 25 } 26 27 int main() 28 { 29 scanf("%d%d",&n,&m); 30 init(); 31 for (int i=1 ; i<=n ; i++){ 32 cur[i]=0;int x; 33 for (int j=1 ; j<=m ; j++){ 34 scanf("%d",&x); 35 if (x==0) cur[i]+=(1<<(m-j)); 36 } 37 } 38 for (int i=1 ; i<=cas ; i++) 39 if (judge(state[i],1)) 40 dp[1][i]=1; 41 for (int i=2 ; i<=n ; i++){ 42 for (int j=1 ; j<=cas ; j++){ 43 if (judge(state[j],i)==false) continue; 44 for (int k=1 ; k<=cas ; k++){ 45 if (judge(state[k],i-1)==false) continue; 46 if (state[k]&state[j]) continue; 47 dp[i][j]=(dp[i][j]+dp[i-1][k])%mod; 48 } 49 } 50 } 51 int maxn=0; 52 for (int i=1 ; i<=cas ; i++) 53 maxn=(maxn+dp[n][i])%mod; 54 printf("%d ",maxn); 55 return 0; 56 }