Sol
很经典的题目还是要写个题解(主要是觉得自己最近越来越懒决定强迫自己更更博
这个题目的要求就是你选的格子如果是$1$,那么它四周的各自不能为$1$。也就是说四个方向上相邻的格子不能有相邻的$1$
注意到$n,m \leq 12$的数据范围很小,考虑状压。
可以设$f[i][j]$表示第$i$行的选$1$的格子状态为$j$时,满足要求的方案数。那么我们可以预处理出所有合法的方案,记作$s[i]$,那么s[i] = (!(i & (i << 1))) && (!(i & (i >> 1)))
那么我们直接枚举第$i$行的状态为$j$时,第$i-1$行的状态为$k$,满足此时$j\&k$且$j$状态选取的$1$格子在给定的网格图上有$1$且保证$j$状态为合法态。
最后直接按照加法原理统计第$n$行所有合法答案即可
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = (1 << 12) + 5;
const int mod = 1e8;
int n, m;
int s[SIZE], g[SIZE], f[SIZE][SIZE], a[SIZE][SIZE];
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using ae86::read;
signed main() {
// freopen("code.in", "r", stdin);
// freopen("code.out", "w", stdout);
n = read(), m = read();
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
a[i][j] = read();
g[i] = (g[i] << 1) + a[i][j];
}
}
int r = (1 << m); f[0][0] = 1;
for (int i = 0; i < r; ++ i) {
s[i] = (!(i & (i << 1))) && (!(i & (i >> 1)));
}
for (int i = 1; i <= n; ++ i) {
for (int j = 0; j < r; ++ j) {
if (s[j] && (j & g[i]) == j) {
for (int k = 0; k < r; ++ k) {
if (!(k & j)) f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
}
}
}
}
int ans = 0;
for (int i = 0; i < r; ++ i) {
ans = (ans + f[n][i]) % mod;
}
printf("%lld\n", ans % mod);
return 0;
}