<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

农夫约翰的土地由 $M \\times N$ 个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式

第 $1$ 行包含两个整数 $M$ 和 $N$。

第 $2..M+1$ 行：每行包含 $N$ 个整数 $0$ 或 $1$，用来描述整个土地的状况，$1$ 表示该块土地肥沃，$0$ 表示该块土地不育。

输出格式

输出总种植方法对 $10^8$ 取模后的值。

数据范围

$1 \\le M,N \\le 12$

输入样例：

2 3
1 1 1
0 1 0

输出样例：

9

思路

这题和小国王思路相同。
我们把所有合法状态算出来，枚举时只枚举合法状态。
我么用$g_i$表示第$i$行是否可用。为了方便判断，我们把原来的图反转一下，即$0/1$反转。
判断时判断当前状态$s$，$s\&g_i$是否为$0$，不为$0$就直接$continue$。

代码

#include <iostream>
#include <vector>
using namespace std;
const int N = 15,M = 1 << N,MOD = 1e9;
int n,m;
int g[N];
int f[N][M];
vector <int> state;
vector <int> h[M];
bool check (int x) {
    for (int i = 0;i < m - 1;i++) {
        if ((x >> i & 1) && (x >> i + 1 & 1)) return false;
    }
    return true;
}
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            bool x;
            cin >> x;
            g[i] = g[i] << 1 | !x;
        }
    }
    for (int i = 0;i < 1 << m;i++) {
        if (check (i)) state.push_back (i);
    }
    for (int i = 0;i < state.size ();i++) {
        for (int j = 0;j < state.size ();j++) {
            int a = state[i],b = state[j];
            if (!(a & b)) h[i].push_back (j);
        }
    }
    f[0][0] = 1;
    for (int i = 1;i <= n + 1;i++) {
        for (int a = 0;a < state.size ();a++) {
            if (!(state[a] & g[i])) {
                for (int b : h[a]) f[i][a] = (f[i][a] + f[i - 1][b]) % MOD;
            }
        }
    }
    cout << f[n + 1][0] << endl;
    return 0;
}