题意 ： 一个m*n的矩形，1代表有草，0代表没有草，将牛放在有草的地方，牛与牛之间不能相邻。问有多少种方法。
思路 ： 状态压缩，从上往下枚举，如果第一行的确定了，那第二行中所有与第一行有草的地方相邻的格子便不能再用，以此类推，只要求出每行可用的方法数，dp[i][j] += dp[i-1][k]。代表的是第 i 行状态为 j 时，等于第i-1行状态为k时加上这一行的状态，当然，j与k中不能有相邻的1.所有的牛都不放也是一种方法，所以可以先对第一行预处理一下，状压时，对每一行的处理取反，后续处理方便。
1 //3254 2 3 #include4 #include 5 #include 6 #include 7 #define mod 100000000 8 9 using namespace std ;10 int dp[15][1 << 15],po[15] ;11 int mp[15][15],d[1 << 15] ;12 13 int main()14 {15 int n, m ;16 po[1] = 1 ;17 for(int i = 2 ; i <= 14 ; i++)18 po[i] = po[i-1] * 2 ;19 while(~scanf("%d %d",&m,&n))20 {21 // memset(dp,0,sizeof(dp)) ;22 // memset(d,0,sizeof(d)) ;23 // int s = m ;24 for(int i = 1 ; i <= m ; i++)25 {26 d[i] = 0 ;27 for(int j = 1 ; j <= n ; j++)28 {29 scanf("%d",&mp[i][j]) ;30 if(!mp[i][j])31 d[i] += po[j] ;32 }33 }34 35 for(int i = 0 ; i < (1 << n) ; i++)36 {37 if((i >> 1) & i || (i << 1) & i)38 continue ;39 if(i & d[1])40 continue ;41 dp[1][i] = 1 ;42 }43 for(int i = 2 ; i <= m ; i++)44 {45 for(int j = 0 ; j < (1 << n) ; j++)46 {47 if((j >> 1) & j || (j << 1) & j)//草地与不能左右草地相邻48 continue ;49 if((d[i] & j))//要枚举的方块必须是草地50 continue ;51 for(int k = 0 ; k < (1 << n) ; k++)52 {53 if((k << 1) & k || (k >> 1) & k)54 continue ;55 if((d[i-1] & k))56 continue ;57 if(! (j & k)){58 dp[i][j] = (dp[i][j] + dp[i-1][k])%mod ;59 }60 }61 }62 }63 int sum = 0 ;64 for(int i = 0 ; i < (1 << n) ; i ++)65 sum = (sum + dp[m][i])%mod ;66 sum %= mod ;67 printf("%d\n",sum) ;68 }69 return 0 ;70 }