算法1

状态压缩dp $O(n^3)$

dp[i][S]表示第i行，集合为S

时间复杂度

$O(n^3)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int m, n;

const int N = 1 << 12;
int g[12][12];
int dp[12][N];

int status[12];

int main(){
    cin >> m >> n;
    const int mod = 1e9;
    for (int i = 0; i<m; i++){
        int state = 0;
        for (int j = 0; j<n; j++){
            cin >> g[i][j];
            state = (state << 1) | !g[i][j];
        }
        status[i] = state;
    }

    int ans = 0;
    for (int s = 0; s < (1 << n); s++) {
        if (!(s&status[0]) && !(s & (s << 1))) {
            dp[0][s] = 1;
            ans++;
        }
    }

    if (m == 1) {
        cout << ans << endl;
        return 0;
    }
    ans = 0;
    for (int i = 1; i < m; i++){
        for (int s = 0; s < (1 << n); s++){
            if (s & status[i]) continue;
            if (s &(s << 1))continue;
            for (int last = 0; last <(1<<n); last++){
                if (!(last & status[i-1]) && !(last&s) ){
                    dp[i][s] += dp[i-1][last];
                    dp[i][s] %= mod;
                }
            }
            if (i == m - 1) ans += dp[i][s];
        }
    }
    ans%= mod;
    cout << ans << endl;
    return 0;
}