暴力出奇迹

预处理一下合法状态, 和哪些状态之间能互转. 计算f[i][j]的时候再去判断某个状态放在某一行是否合法.

#include <iostream>
using namespace std;

const int N = 14, M = 1 << 12, MOD = 1e8;

int n, m;
bool g[N][N];
int f[N][M];
bool st[M], mv[M][M];

bool checkstate(int state) {
    for (int i = 0; i < m; i++)
        if (((state >> i) & 1) && (state >> i + 1) & 1) return false;
    return true;
}

bool check(int row, int state) {
    if (!checkstate(state)) return false;

    for (int i = 1; i <= m; i++) {
        if (!g[row][i] && (state >> (m - i) & 1)) return false;
    }
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];

    // 两种方案能互转(可能不能放到任意 两行)
    for (int i = 0; i < 1 << m; i++) {
        if (checkstate(i)) st[i] = true;
        if (st[i]) {
            for (int j = 0; j < 1 << m; j++) {
                if (checkstate(j) && (i & j) == 0)  // 这里不需要check(i | j)了, 因为这样的方案也是合法的
                    mv[i][j] = mv[j][i] = true;
            }
        }
    }

    f[0][0] = 1;
    for (int i = 1; i <= n + 1; i++)
        for (int j = 0; j < 1 << m; j++)
            if (st[j] && check(i, j)) {
                for (int k = 0; k < 1 << m; k++) {
                    if (st[k] && check(i - 1, k) && mv[k][j])
                        f[i][j] = (f[i][j] + f[i - 1][k]) % MOD;
                }
            }

    cout << f[n + 1][0] << endl;
    return 0;
}