剛開始的思路是 ?把0-2^x的 所有狀態枚舉， 然后找符合條件的， ? 但是 發現 當12*12 時 ?1的數量x 超過64 ?這是個龐大的數字， 跟本就沒法枚舉；
想到用狀態壓縮， ?但是 怎么壓縮才行 ？
poj1208？
作為這是狀態壓縮入門題， ?感覺 廢了好大力氣；
【思路】
?把每一行 ?0/1狀態 ?轉換成 十進制的數， 每一行看成一個整體， 進行壓縮， ?
poj2106，【第一步】
? 先提前處理 ?相鄰兩項不符合條件的 ?例如 ? 001 和 011 ?這樣的就不符合 （違背相鄰兩項不種植條件）
【第二步】
為了可以找到符合條件的， ?在進行輸入時 處理， ?把 ?輸入的 ?010 ?進行 取反 ?得到的是 ?101 ? ?目的是 & =0； ?找到當前行 滿足條件的
例如 示例 第二行 010， ?那么只有 010 和 000 才能放在這 ? 010 取反為 101 ?， ?101 & 010 ?=0 ? ? ? 101 & 000 =0 ? ?這是符合條件的
空氣壓縮會變成什么。【第三步】
找到當前行符合條件的， ?那么進行篩選， 篩選出 既不能與前一行 相鄰， 又不能與 之前到找的 重復 ?；
找到后 累加到當前行中， 用dp【】【】 存儲?
dp【i】【j】 ?代表 第 i 行 ?狀態 j 時 ?符合條件數目；
?方程 dp【i】【j】 = Sigma? ?dp 【i-1】【k】 ? k代表所有符合的 項
poj2352？
【代碼】
//#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <stdlib.h>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#define mem(a,b) memset(a,b,sizeof(a))
#define findx(x) lower_bound(b+1,b+1+bn,x)-b
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w",stdout)
#define S1(n) scanf("%d",&n)
#define SL1(n) scanf("%I64d",&n)
#define S2(n,m) scanf("%d%d",&n,&m)
#define SL2(n,m) scanf("%I64d%I64d",&n,&m)
#define Pr(n) printf("%d\n",n)
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid + 1, r#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;const int INF=0x3f3f3f3f;
const ll MOD=1e8;
const int MAXN=1e5+5;
const int N=1000;
ll qpow(ll x,ll n){ll res=1;for(;n;n>>=1){if(n&1)res=(res*x);x=(x*x);}return res;}
using namespace std;int dp[N][N];
int cur[MAXN];
int state[MAXN];
int cot;
int n,m;
void init()
{int bits= 1<<m;cot=0;for(int i=0;i<bits;i++){if( (i&(i<<1))==0 )// 去除相鄰的兩項state[++cot]=i;}
}
int main()
{while(~scanf("%d %d",&n,&m)){init();//提前處理所以不相鄰的數據for(int i=1;i<=n;i++){int x;for(int j=1;j<=m;j++){scanf("%d",&x);if(x==0){cur[i]+= (1<< (m-j)); // 取反 目的是 將 后面的重復項去掉， 例如 010 取反為 101 & 010 =0}}}mem(dp,0);for(int i=1;i<=cot;i++){if( (state[i]&cur[1]) ==0)// 邊界狀態dp[1][i]=1;}/* for(int i=1;i<=cot;i++){printf("%d | %d\n",state[i],cur[i]);}*/for(int i=2;i<=n;i++)// 從第二行開始{for(int j=1;j<=cot;j++){if( (state[j]&cur[i])==0 ) //符合條件 當前行{for(int k=1;k<=cot;k++){if( ((state[k]&cur[i-1])==0) && ((state[k]&state[j])==0 ) )// 并且不與前一行重復，找到的兩個值一樣{//printf("%d***\n",state[k]);dp[i][j]= (dp[i][j]+ dp[i-1][k]) %MOD;}}}}}int ans=0;for(int i=1;i<=cot;i++)ans = (ans+dp[n][i])% MOD;printf("%d\n",ans);}
}
/*
12 12
1 0 1 0 1 0 1 0 1 1 1 1
0 0 1 0 0 1 0 0 0 1 1 1
1 0 0 0 1 1 0 1 0 0 0 1
1 0 1 1 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 1 0 1 0 1 0 1
1 1 0 1 0 1 1 0 1 0 1 0
0 0 0 1 0 1 0 1 0 1 0 0
1 0 0 0 1 0 1 0 1 0 0 0
1 0 1 0 1 0 1 1 0 1 0 1
*/
