题目大意
给定一个N*M大小的土地，土地有肥沃和贫瘠之分(每个单位土地用0,1来表示贫瘠和肥沃)，要求你在肥沃的单位土地上种玉米，如果在某个单位土地上种了玉米，那么与它相邻的四个单位土地是不允许种玉米的，问你有多少种种玉米方案。(不种一算一种方案)
题解
很基础的状态压缩DP，我们可以逐行的进行状态转移，用二进制来表示一行的状态，方程表示为：dp[i]j]+=dp[i-1][k],表明我们可以从上一行的状态k转移到当前行的状态j,那怎么样的k才是符合情况的呢？只需要j&k==0即可，也就是玉米不能够种在同一列，由于种的玉米不能够相邻,因此我们的j还需要满足在二进制中不存在相邻的两个1,表达式为(j&(j>>1),题目还有一个要求就是只能种在肥沃的土地上,我们用一个二进制来表示某一行的肥沃和贫瘠状态(假设为s),那么j需要满足是s的一个子集,这个要怎么判断呢？其实也很简单，只需(j&s)==j就说明j是s的子集
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 15
#define MOD 100000000
int dp[MAXN][1<<MAXN],line[MAXN];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(line,0,sizeof(line));
for(int i=1;i<=n;i++)
for(int j=0;j<m;j++)
{
int a;
scanf("%d",&a);
line[i]|=a<<j;
}
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<(1<<m);j++)
if((j&line[i])==j&&((j&(j>>1))==0))
for(int k=0;k<(1<<m);k++)
if((j&k)==0)
dp[i][j]+=dp[i-1][k];
int ans=0;
for(int i=0;i<(1<<m);i++)
ans+=dp[n][i];
printf("%d\n",ans%MOD);
}
return 0;
}