Link

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;
}