题意：在n*m方格中种草，每两处种草的格子不能相邻，并且不能在贫瘠的土壤中种植(a[i][j]==1)，问有多少种方案
思路：用dp[i][j]表示i行状态为j时有多少种方案，当两个1不相邻，并且bit==1时a[i][j]=1，状态j合法。
对于每个合法状态dp[i][j]，遍历i-1行所有的状态，若j可由k状态转移而来，dp[i][j]+=dp[i-1][k]。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #define LL long long #define eps 1e-8 #define maxn 150 #define mod 110119 #define inf 0x3f3f3f3f #define IN freopen("in.txt","r",stdin); using namespace std; int n,m; int a[13][13]; bool OK(int i,int j){ //第i行j状态能否合法 for(int k=0;k<m;k++){ // if(j & 1<<k && a[i][k+1]==0) //在贫瘠的土壤上种植 return false; } for(int k=0;k<m-1;k++){ if(j& 1<<k && (j & 1<<(k+1))){ //两位1相邻 return false; } } return true; } bool YES(int j,int k){ //k能转移到j for(int i=0;i<m;i++){ if(k & (1<<i) && (j &(1<<i)) ){ return false; } } return true; } int main(){ // IN; cin>>n>>m; int dp[13][1<<13]; memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } dp[0][0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<1<<m;j++){ if(OK(i,j)){ //j合法 for(int k=0;k<1<<m;k++){ //遍历上行所有状态 if(YES(j,k)){ dp[i][j]+=dp[i-1][k]; } } } } } LL ans=0; for(int i=0;i<1<<m;i++){ ans+=dp[n][i]; } ans%=100000000; cout<<ans<<endl; }
