C++ 代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int n, m, k, i, j,  nn;
int a[12], b1[13][4100], b2[4100][4100], d[13][13];
long long f[13][4100];

void two(int s)//二进制化被压缩的状态
{
    for (int i = 0; i < n; i++)
    {
        a[i] = s % 2;
        s /= 2;
    }
}

bool calb1(int s,int h)//判断1行是否合法
{
    two(s); int i;
    for (i = 0; i < n - 1; i++)
        if (a[i] + a[i + 1] == 2)return 0;
    for (i = 0; i < n; i++)if (d[h][i + 1]==0 && a[i] == 1)return 0;
    return 1;
}

bool calb2(int s1, int s2)//判断2行之间是否合法
{
    s1 = s1&s2; if (s1) return 0;
    return 1;
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin >> m>> n;
    for (i = 1; i <= m; i++)for (j = 1; j <= n; j++)cin >> d[i][j];
    f[0][0] = 1;//不放也是一种状态
    nn = 1;
    for (i = 0; i < n; i++)nn *= 2;//状态的最大数目
    for (j = 1; j <= m;j++)
    for (i = 0; i < nn; i++)b1[j][i] = calb1(i,j);//DP思想,存在表中避免重复计算
    b1[0][0] = 1;//初始化一种合法的状态
    for (i = 0; i < nn; i++)for (j = 0; j < nn; j++)
        b2[i][j] = calb2(i, j);
    for (i = 1; i <= m; i++)
        for (j = 0; j < nn; j++)
            if (b1[i][j])
                for (int s = 0; s < nn; s++)
                    if (b1[i - 1][s] && b2[s][j])
                        f[i][j] += f[i - 1][s];
    int sum = 0;
    for (i = 0; i < nn; i++)sum += f[m][i];
    cout << sum%1000000000;
    return 0;
}