AcWing 327. 玉米田
原题链接
简单
作者:
wangyj
,
2021-01-18 20:12:10
,
所有人可见
,
阅读 309
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int mod=1e8;
int n,m,w[14],f[14][1<<12];
vector<int>state,head[1<<12];
bool check(int state)
{
for(int i=0;i+1<m;i++)if((state >> i & 1)&&(state >> i + 1 & 1))return false;
return true;
}
int main()
{
int i,j,a,b,t;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)for(j=0;j<m;j++){
scanf("%d",&t);
w[i]+=!t*(1 << j);
}
for(i=0;i< 1 << m;i++)if(check(i))state.push_back(i);
for(i=0;i<state.size();i++)for(j=0;j<state.size();j++){
a=state[i],b=state[j];
if(!(a&b))head[i].push_back(j);
}
f[0][0]=1;
for(i=1;i<=n+1;i++)for(j=0;j<state.size();j++)if(!(state[j]&w[i]))
for(int k:head[j])f[i][j]=(f[i][j]+f[i-1][k])%mod;
printf("%d\n",f[n+1][0]);
return 0;
}