大意:
给N*M的棋盘,每个格子不是0就是1,1代表可以种草,否则不能。相邻两个格子不能同时种草,求种草的方案总数
要点:
表示第
行在状态
(用二进制数表示)的时候的方案数
(k为不冲突的状态)
(num为状态总数)
- 初始条件:
#include<bits/stdc++.h> #define ll long long using namespace std; int n,m,dp[13][401],a[13][13],s[13]; const int mod =1e8; vector<int> v; int main(){ cin>>n>>m; for(int i = 0;i<1<<m;i++)//从0开始才能枚举所有情况 if(((i<<1)&i)==0) v.push_back(i); for(int i = 1;i<=n;i++) for(int j = 0;j<m;j++) scanf("%d",&a[i][j]),s[i] = (s[i]<<1)+a[i][j]; dp[0][0] = 1;//方案数最少是1 for(int i = 1;i<=n;i++)//以行作为阶段 for(int j = 0;j<v.size();j++)//枚举第i行状态 if((v[j]&s[i])==v[j])//保证适合种草:v[j]每一个1位对应s[i]相同位置必须是1 for(int k = 0;k<v.size();k++)//枚举第i-1行状态 if((v[k]&v[j])==0){ dp[i][j]+=dp[i-1][k]; dp[i][j]%=mod; } ll ans = 0; for(int i = 0;i<v.size();i++) ans = (ans+dp[n][i])%mod; cout<<ans; return 0; }