题目大意：有一个$n\times m$的矩阵，$(1 \leq m \leq 12; 1 \leq n \leq 12)$，想在其中的一些格子中种草，一些格子不能种草，且两块草地不相邻。问有多少种种植方案。
题解：状压$DP$，$f_{i,j}$表示处理到了第$i$行，当前状态为$j$的方案数
卡点：无
C++ Code：
#include <cstdio>
using namespace std;
const int mod = 100000000;
int n, m, a;
int p[13], s[5000], tot;
int f[13][1 << 12];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &a);
if (a) p[i] |= 1 << j;
}
}
for (int i = 0; i < 1 << m; i++) {
if (!(i & (i << 1))) {
s[tot++] = i;
if ((i | p[1]) == p[1]) f[1][i]++;
}
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j < tot; j++) {
if ((s[j] | p[i - 1]) == p[i - 1]) {
for (int k = 0; k < tot; k++) {
if (((s[k] & s[j]) == 0) && ((s[k] | p[i]) == p[i])) {
f[i][s[k]] = (f[i][s[k]] + f[i - 1][s[j]]) % mod;
}
}
}
}
}
int ans = 0;
for (int i = 0; i < tot; i++) ans = (ans + f[n][s[i]]) % mod;
printf("%d\n", ans);
return 0;
}