农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。
遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。
John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
输入格式：
第一行：两个整数M和N，用空格隔开。
第2到第M+1行：每行包含N个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。
输出格式：
一个整数，即牧场分配总方案数除以100,000,000的余数。
代码解释：
/***********************************************/
const int maxn= 4096;
bool ju[maxn+6];//判断此方案是否符合草地不连续
int dp[20][maxn+6];//对第i行状态j时，前i行的方案数
int maps[20];//二进制地图
int main()
{
int m,n;
cin>>m>>n;
int a;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++) {
cin>>a;
maps[i]=(maps[i]<<1)+a;
}
}
int maxnn=(1<<n)-1;
for(int i=0;i<=maxnn;i++)
if(((i&(i<<1))==0) && ((i&(i>>1))==0)) ju[i]=true;//可行
//说明i方案二进制没有相邻的两个1
//预处理dp第一行
for(int j=0;j<=maxnn;j++)
if( (ju[j]) && ( (j & maps[1]) ==j) ) dp[1][j]=1;
/*
(j & maps[1]) ==j //必须打括号，&优先级低于==（这是个WA点...）
它用来判断maps[1]二进制的1是否包含了j中的1
如：maps[1] :1001101
j :1000100
所以：& :1000100
如果 & 操作后值为j，则表示j方案在地图map上可行
*/
for(int i=2;i<=m;i++)
{
for(int j=0;j<=maxnn;j++)//枚举i行的每个状态
{
if( (ju[j]) && ( j & maps[i]) ==j)
{//再判断和前面的行会不会冲突
//不冲突就都加上
for(int k=0;k<=maxn;k++)
if((j&k)==0)//不冲突
dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
}
}
}
ll ans=0;
for(int j=0;j<=maxnn;j++) ans=(ans+dp[m][j])%mod;
cout<<ans<<endl;
return 0;
}
原文：https://www.cnblogs.com/liuyongliu/p/10327921.html