题意:
n*m网格1能放0不能放 放的格子不能相邻 求一共多少种可放的方案。
分析：
dp[i][j]第i行可行状态j的的最大方案数，枚举当前行和前一行的所有状态转移就行了（不放牛也算一种情况）
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = 100000000;
int dp[15][5000],n,m,a[15][15];
int judge(int i,int x){int t=x;int m1=m;while(m1--){if((x&1)&&a[i][m1]==0)return 0;x>>=1;}if(((t<<1)&t)==0&&((t>>1)&t)==0){return 1;}return 0;
}
void solve(){memset(dp,0,sizeof(dp));for(int i=0;i<(1<<m);++i){if(judge(0,i))dp[0][i]=1;}for(int i=1;i<n;++i){for(int j=0;j<(1<<m);++j){for(int k=0;k<(1<<m);++k)if(judge(i,j)&&judge(i-1,k)&&(j&k)==0)dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;}}int total=0;for(int i=0;i<(1<<m);++i)total=(total+dp[n-1][i])%mod;printf("%d\n",total);
}
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=0;i<n;i++)for(int j=0;j<m;++j)scanf("%d",&a[i][j]);solve();}
return 0;
}
