状压DP，种树

有一块土地，准备用来种果树，这块土地可以分割为N * M块，每一块种一颗果树。为了保证果树存活成长，需要避免两种情况:
1.相邻地块同时种植果树;
2.在岩石地块种植果树;

求共有多少种果树种植方式?

输入描述:
首行输入两个以空格分开的整数N，M (1<-N,M<=10)，接下来是N行每行M个整数.0表示该地块是岩石地块，不适合种植果树，1表示适合种植果树。

输入示例：
2 3
1 1 1
0 1 0
输出：
8

用一个数来表示一组数，以降低表示状态所需的维数的解题手段，就叫做状态压缩。

通过对样例数据的分析即可以发现不同状态之间的关系：
以dp[i][state(j)]来表示对于前i行，第i行采用第j种状态时可以得到的可行方案总数！
例如：回头看样例数据，dp[2][1]即代表第二行使用第2中状态（0 1 0）时可得的方案数，即为4；
那么，可得出状态转移方程为：
dp[i][state(j)]=dp[i-1][state(k1)]+dp[i-1][state(k2)]+......+dp[i-1][state(kn)](kn即为上一行可行状态的编号，上一行共有n种可行状态）
最终ans=dp[m][state(k1)]+dp[m][state(k2)]+......+dp[m][state(kn)]; (kn即为最后一行（第m行）可行状态的编号）

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 12
#define mod 100000000
using namespace std;
int dp[N+1][1<<N];  ///dp[i][j]表示当第i行的状态为j时前i行的放牛方案总数
int state[1<<N]; ///保存所有的合法状态数
int cur[N+1]; ///每一行的状态,注意这里保存的是0,因为当我们保存0时,如果某一状态与当前行相与不为0，那么
///就能判断出那个状态是不合法的(假设那个位置不应该种草，而它种了草)
int n,m;
bool check(int k){
    if(k&(k<<1)) return false;
    return true;
}
void init(int &k){
    for(int i=0;i<(1<<m);i++){
        if(check(i)) state[++k]=i;
    }
    //printf("%d\n",k);
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        int k = 0;
        init(k);
        int num;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            cur[i]=0;
            for(int j=1;j<=m;j++){
                scanf("%d",&num);
                if(num==0) cur[i]+=(1<<(j-1));
            }
        }
        for(int i=1;i<=k;i++){
            if(!(cur[1]&state[i])){
                dp[1][i]=1;
            }
        }
        for(int i=2;i<=n;i++){
            for(int j=1;j<=k;j++){
                if(cur[i]&state[j]) continue; ///枚举第i行的可行状态state[j]
                for(int t = 1;t<=k;t++){
                    if(cur[i-1]&state[t]) continue; ///枚举第i-1行的可行状态state[t]
                    if(state[j]&state[t]) continue; ///判断相邻两行状态是否合法
                    dp[i][j] = (dp[i][j]+dp[i-1][t]+mod)%mod;
                }
            }
        }
        int ans = 0;
        for(int i=1;i<=k;i++){
            ans = (ans+dp[n][i]+mod)%mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}