有一塊土地字币，準(zhǔn)備用來種果樹，這塊土地可以分割為N * M塊共缕，每一塊種一顆果樹洗出。為了保證果樹存活成長，需要避免兩種情況:
1.相鄰地塊同時(shí)種植果樹;
2.在巖石地塊種植果樹;

求共有多少種果樹種植方式?

輸入描述:
首行輸入兩個(gè)以空格分開的整數(shù)N图谷，M (1<-N,M<=10)翩活，接下來是N行每行M個(gè)整數(shù).0表示該地塊是巖石地塊，不適合種植果樹便贵，1表示適合種植果樹菠镇。

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

用一個(gè)數(shù)來表示一組數(shù)，以降低表示狀態(tài)所需的維數(shù)的解題手段嫉沽，就叫做狀態(tài)壓縮辟犀。

通過對樣例數(shù)據(jù)的分析即可以發(fā)現(xiàn)不同狀態(tài)之間的關(guān)系：
以dp[i][state(j)]來表示對于前i行俏竞，第i行采用第j種狀態(tài)時(shí)可以得到的可行方案總數(shù)绸硕！
例如：回頭看樣例數(shù)據(jù)，dp[2][1]即代表第二行使用第2中狀態(tài)（0 1 0）時(shí)可得的方案數(shù)魂毁，即為4玻佩；
那么，可得出狀態(tài)轉(zhuǎn)移方程為：
dp[i][state(j)]=dp[i-1][state(k1)]+dp[i-1][state(k2)]+......+dp[i-1][state(kn)](kn即為上一行可行狀態(tài)的編號席楚，上一行共有n種可行狀態(tài)）
最終ans=dp[m][state(k1)]+dp[m][state(k2)]+......+dp[m][state(kn)]; (kn即為最后一行（第m行）可行狀態(tài)的編號）

#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]表示當(dāng)?shù)趇行的狀態(tài)為j時(shí)前i行的放牛方案總數(shù)
int state[1<<N]; ///保存所有的合法狀態(tài)數(shù)
int cur[N+1]; ///每一行的狀態(tài),注意這里保存的是0,因?yàn)楫?dāng)我們保存0時(shí),如果某一狀態(tài)與當(dāng)前行相與不為0咬崔，那么
///就能判斷出那個(gè)狀態(tài)是不合法的(假設(shè)那個(gè)位置不應(yīng)該種草，而它種了草)
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行的可行狀態(tài)state[j]
                for(int t = 1;t<=k;t++){
                    if(cur[i-1]&state[t]) continue; ///枚舉第i-1行的可行狀態(tài)state[t]
                    if(state[j]&state[t]) continue; ///判斷相鄰兩行狀態(tài)是否合法
                    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;
}