POJ 3254 Corn Fields (状态压缩DP）

看了好几回状态压缩dp了，也看了不少博客，今天经过贺贺的讲解对位运算有了认识，参考了一下贺贺的博客，终于做了第一道状态压缩dp题，还要努力( ⊙ o ⊙ )啊……

状态压缩dp的一个很好的博客：http://blog.csdn.net/accry/article/details/6607703

题意：一个n*m的矩阵，每个格子是0或者1，1表示土壤肥沃可以种植草地，0则不可以。在种草地的格子可以放牛，但边相邻的两个格子不允许同时放牛，问总共有多少种放牛的方法？（不放牛也算一种情况）

AC代码如下

 1 //注意位运算符优先级很低
 2  #include<stdio.h>
 3  #include<string.h>
 4  #define mo 100000000
 5  int corn[15],dp[15][1<<13];
 6  
 7  int ok(int x,int y)
 8  {
 9      if((x&y)!=x)  return 0;//判断牛的状态和草地是否匹配
10      if(x&(x<<1))  return 0;//判断左右是否相邻
11      return 1;
12  };
13  
14  int main()
15  {
16      int n,m,i,j,k,t,ans;
17      while(~scanf("%d%d",&n,&m))
18      {
19          memset(corn,0,sizeof(corn));
20          for(i=1; i<=n; i++)
21          {
22              for(j=0; j<m; j++)
23              {
24                  scanf("%d",&t);
25                  corn[i]=(corn[i]<<1)+t;//corn表示草地的状态情况
26              }
27          }
28  
29          memset(dp,0,sizeof(dp));
30  
31          for(j=0; j<(1<<m); j++)//初始第一行草地
32              if(ok(j,corn[1]))
33                  dp[1][j]=1;
34  
35          for(i=2; i<=n; i++)
36              for(j=0; j<(1<<m); j++)
37              {
38                  if(ok(j,corn[i]))
39                      for(k=0; k<(1<<m); k++)
40                          if((j&k)==0)//判断是否与上一行相邻
41                              dp[i][j]=(dp[i][j]+dp[i-1][k])%mo;//状态方程，并按题意取余
42              }
43  
44          ans=0;
45          for(j=0; j<(1<<m); j++)
46              ans=(ans+dp[n][j])%mo;//将所有情况加起来
47  
48          printf("%d\n",ans);
49      }
50  }
51