题意:
给出一个n×m的玉米地,即一个01矩阵,1上的格子可以种地,0不可以,两个相邻的格子不能同时种地,求种地的方案数。
题解:
状压dp;
由于每一行的状态受到上一行的限制,所以肯定要考虑枚举这一行的状态和上一行的状态;
而当前这一行的状态又会受到一些限制,所以考虑如何防止不合法的状态被转移到;
1、没有相邻玉米地的状态,这个可以预处理判断;
2、当前这一行的状态必须是原图的一个子集;
3、判断上一行和这一行没有相邻的玉米地;
三个同时成立即可转移
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define N 13
#define mo 100000000
using namespace std;
int dp[N][1<<N],g[1<<N],f[N];
int gi() {
int x=0,o=1; char ch=getchar();
while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
if(ch=='-') o=-1,ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return o*x;
}
int main() {
int n=gi(),m=gi(),ans=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
int x=gi();
f[i]=(f[i]<<1)+x;//状压这一行的状态
}
for(int s=0; s<1<<m; s++) {
if(!((s<<1)&s && (s>>1)&s)) g[s]=1;//1、判断这一行是否有两个相邻的草地
}
dp[0][0]=1;
for(int i=1; i<=n; i++) {
for(int s=0; s<1<<m; s++) {
if((s&f[i])==s && g[s]) {//2、第一个条件成立当且仅当s是t[i]的一个子集
for(int k=0; k<1<<m; k++) {//k若不合法,则不会被转移,所以不判断k是否合法也无妨
if(!(s&k)) (dp[i][s]+=dp[i-1][k])%=mo;//3、上下不相交
}
}
}
}
for(int s=0; s<1<<m; s++) {
(ans+=dp[n][s])%=mo;
}
printf("%d", ans);
return 0;
}