题意：
约翰有一个N*M的农场，他想在里面种小麦。
有些格子是不育的，并且两株小麦不能相邻（上下或左右）。
问种植的方案有多少种，一个也不种植也是一种方案。
思路：
非常裸的一道状压dp，但是复杂度把人吓住了。
首先枚举当前状态cur，再枚举之前的状态pre，对于每一行都这样做。
那么复杂度就是O(n (2^m) (2^m))。
但是这样确实过了，以后写题，要敢于暴力。
状态转移方程：
dp[i][cur] = sum{dp[i-1][pre]} (cur与pre不冲突)。
代码：
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 const int N = 14; 6 const int mod = 100000000; 7 int dp[N][(1<<N)]; 8 int mp[N][N]; 9 bool judge(int x,int m,int k) 10 { 11 if (x & (x<<1)) return 0; 12 for (int i = 0;i < m;i++) 13 { 14 if (!mp[k][i] && (x&(1<<i))) return 0; 15 } 16 return 1; 17 } 18 int main() 19 { 20 int n,m; 21 while (scanf("%d%d",&n,&m) != EOF) 22 { 23 memset(dp,0,sizeof(dp)); 24 for (int i = 0;i < n;i++) 25 { 26 for (int j = 0;j < m;j++) scanf("%d",&mp[i][j]); 27 } 28 for (int i=0;i<(1<<m);i++) 29 { 30 if (judge(i,m,0)) dp[0][i] = 1; 31 } 32 for (int i = 1;i < n;i++) 33 { 34 for (int j = 0;j < (1<<m);j++) 35 { 36 if (!judge(j,m,i-1)) continue; 37 for (int k = 0;k < (1<<m);k++) 38 { 39 if (!judge(k,m,i)) continue; 40 if (j&k) continue; 41 dp[i][k] = (dp[i][k] + dp[i-1][j]) % mod; 42 } 43 } 44 } 45 int ans = 0; 46 for (int i = 0;i < (1<<m);i++) 47 { 48 ans = (ans + dp[n-1][i]) % mod; 49 } 50 printf("%d\n",ans); 51 } 52 return 0; 53 }