acw327.玉米田

题意：

有土地有$m*n$个小方格组成，现在要在土地中种植玉米。
部分土地是不育的，无法种植。
相邻的土地不能同时种植玉米，也就是种植玉米的所有方格之间都不会有公共边缘。
现在给定土地的大小，请你求出有多少种种植方法。
土地上什么都不种也算是一种方法。
输入一个二维矩阵，1表示这个土地肥沃，0表示土地贫瘠。
数据范围：$n,m\leq 12$。

思路：

状压$dp$。
设$F(i)$表示第$i$行草地的情况，这里的$F$数组中存的是二进制数。
然后我们从0~MAXSTATE这些状态里找到合法的状态，也就是不能两个玉米地是相邻的。

然后开始dp。
从第一行开始，每行找所有状态，如果这个状态是合法的，且不在贫瘠的土地上，那么接下来找上一行合法的情况（上下两行没有相邻的土地），把上一行的答案加到这一行中。
最后把最下面一行的答案统计起来，就是答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e8;
const int maxn = 15;
int n, m, a[maxn][maxn];
ll f[maxn][1<<maxn];
ll F[maxn];
bool state[1<<maxn];
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            F[i] = (F[i]<<1) + a[i][j];
    int maxstate = 1<<m;
    for(int i = 0; i < maxstate; i++)
        state[i] = ((i&(i<<1))==0) && ((i&(i>>1))==0);
    //表示i这个状态两两之间没有相邻的
    //什么也没种也是一种方案
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < maxstate; j++)
            //这一行这个方案是合法的
            //且没有在贫瘠的土地上种植
            if(state[j] && ((j & F[i]) == j))
                //枚举上一行的状态
                for(int k = 0; k < maxstate; k++)
                    if((k & j) == 0) //和上一行没有相邻
                    f[i][j] = (f[i][j] + f[i-1][k]) % mod;
    ll ans = 0;
    for(int i = 0; i < maxstate; i++)
        ans += f[n][i], ans %= mod;
    cout << ans << endl;
    return 0;
}