添加链接描述
状压DP。
#include<bits/stdc++.h>
#define ll long long
#define x first
#define y second
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
using namespace std;
const int M=15,INF=0x3f,mod=1e8;
ll a[M],dp[M][1<<M];
vector<int>judge;
vector<int>state[1<<M];
bool check(int state)
{
return !((state&state<<1));
}
int main()
{
int m,n;
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=0;j<n;j++)
{
int k;
cin>>k;
a[i]|=!k<<j;
}
for(int j=0;j<1<<n;j++)
if(check(j))
judge.push_back(j);
for(auto i:judge)
for(auto j:judge)
if(!(i&j))
state[i].push_back(j);
dp[0][0]=1;
for(int i=1;i<=m+1;i++)
for(auto j:judge)
if(!(a[i]&j))
for(auto k:state[j])
dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
cout<<dp[m+1][0]<<endl;
return 0;
}
