题目大意：这块牧场被划分成 M 行 N 列 (1≤M≤12,1≤N≤12)，每一格都是一块正方形的土地。 在这些土地上种草。有些土地不能用来种草，且草地之间不相邻一共有多少种种植方案可供他选择？（把新牧场完全荒废也是一种方案）

一个典型的状压DP问题，首先，确定每一行有哪些状态是可行的，那么对于每一行的某个状态sta，要满足两个条件

1. 没有草地相邻，即sta & sta >> 1。
2. 选中的草地都可以用来种草，即sta | a[i] == a[i]，a[i]表示第i行的草地状态。

这样就可以选出有哪些状态符合条件

for(int i = 1;i <= n;++i)
	for(int j = 0;j <= (1 << m);++j)
		if(!(j & j << 1) and (j | a[i].to_ulong()) == a[i].to_ulong())
			s[i].push_back(j);

接着就可以开始计算总数了，这里有两种方法，首先最容易想到的就是DFS搜索，枚举每一行的每一种状态，符合条件的就接着向下搜索，在最后一行计数。

for(int sta : s[1])
    dfs(1,sta);

void dfs(int lin,int status){
    if(lin == n){
        total = (total + 1) % MOD;
        return;
    }
    for(int sta : s[lin + 1])
        if(!(status & sta))
            dfs(lin + 1,sta);
}

但是这种方法显然会超时，那么就只能用另一种方法，动态规划。

我们设状态 $f(i,j)$ 为第i行状态为j的情况下的总方案数，那么状态转移方程为
$$f(i,j)=\sum _{!(j\&k)}f(i-1,k)$$
最后将第n行的所有状态的总方案数相加即可。

for(int sta : s[1])
	f[1][sta] = 1;
for(int i = 2;i <= n;++i)
	for(int j : s[i])
		for(int k : s[i - 1])
			if(!(j & k))
				f[i][j] = (f[i][j] + f[i - 1][k]) % MOD;
for(int sta : s[n])
	total = (total + f[n][sta]) % MOD;
total %= MOD;

完整代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 15,MOD = 100000000;
int n,m;
ll f[N][1 << N],total = 0;
bitset<N> a[N];
vector<int> s[N];

int main(){
    cin >> n >> m;
    int t;
    for(int i = 1;i <= n;++i){
        for(int j = 0;j < m;++j){
            cin >> t;
            a[i][j] = t == 1;
        }
    }
    for(int i = 1;i <= n;++i)
        for(int j = 0;j <= (1 << m);++j)
            if(!(j & j << 1) and (j | a[i].to_ulong()) == a[i].to_ulong())
                s[i].push_back(j);
    for(int sta : s[1])
        f[1][sta] = 1;
    for(int i = 2;i <= n;++i)
        for(int j : s[i])
            for(int k : s[i - 1])
                if(!(j & k))
                    f[i][j] = (f[i][j] + f[i - 1][k]) % MOD;
    for(int sta : s[n])
        total = (total + f[n][sta]) % MOD;
    total %= MOD;
    cout << total << endl;

    return 0;
}