题目描述

算法1

(暴力枚举) $O(n^2)$

注释版，仅记录

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

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

int n,m;
int w[N];   
vector<int> state;
vector<int> head[M];
int f[N][M];

bool check(int state)   //检查本状态是否能符合题意
{
    for(int i=0;i+1<m;i++)
    {       //不允许存在相邻两个1
        if((state>>i &1) && (state>>i+1 &1))
            return false;
    }
    return true;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            int t;
            cin >> t;
            w[i] += !t * (1 << j);  //把图用二进制表示出来，是1的位置不能选，方便做与运算。
        }

    for (int i = 0; i < 1 << m; i ++ )
        if (check(i))
            state.push_back(i);

    for (int i = 0; i < state.size(); i ++ )
        for (int j = 0; j < state.size(); j ++ )
        {
            int a = state[i], b = state[j];
            if (!(a & b))       //这一行和上一行没有交集，a就可以转移到b
                head[i].push_back(j);
        }

    f[0][0]=1;
    for(int i=1;i<=n+1;i++)
    {
        for(int j=0;j<state.size();j++) //
        {
            if(!(state[j] & w[i]))  //w[i]的1不能放，state[j]的i表示要放，所以&一下，结果是1就不合法。
            {
                for(int k:head[j])
                {
                    f[i][j]=(f[i][j]+f[i-1][k])%mod;
                }
            }
        }
    }

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

    return 0;
}