题目描述

农夫约翰的土地由M*N个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式

第1行包含两个整数M和N。

第2..M+1行：每行包含N个整数0或1，用来描述整个土地的状况，1表示该块土地肥沃，0表示该块土地不育。

输出格式

输出总种植方法对100000000取模后的值。

数据范围

$1≤M,N≤12$

输入样例

2 3
1 1 1
0 1 0

输出样例

9

状压dp

状态表式：①集合：$f[i][j]$表示第$i$行玉米种植状态为$j$的集合。②属性：数目
状态计算：$f[i][j]+=f[i-1][k]$
第$i-1$行状态$k$可以转移到第$i$行状态$j$。

限制条件

①同一行不能有相邻土地都种植玉米，同行约束即(j&j<<1)==0
②同一列不能有相邻土地都种植玉米，同列约束即(j&k)==0
③不能在不育的土地上种植玉米，土地约束check(i,j)

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=14,M=1<<N,mod=100000000;
typedef long long ll;
ll f[N][M];
int n,m;
bool g[N][N];
bool check(int i,int j)//表示第i行玉米种植状态是j的情况
{
    if(i==0) return 1;//如果第0行直接满足
    int t=m;
    //j是个01串例如01010100010。1表示该位置种植玉米，0表示不种植
    //遍历每个地的玉米是否符合土地约束
    while(j)
    {   //这个地方种玉米但是土地不育
        if((j&1)&&!g[i][t]) return 0;
        j>>=1;
        t--;
    }
    return 1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>g[i][j];
    f[0][0]=1;

    for(int i=1;i<=n+1;i++) 
        for(int j=0;j<1<<m;j++)
            if((j&j<<1)==0&&check(i,j))//同行约束+土地约束
                for(int k=0;k<1<<m;k++)
                    if((k&k<<1)==0&&(k&j)==0&&check(i-1,k))//同行约束+同列约束+土地约束
                    {
                        f[i][j]+=f[i-1][k];
                        f[i][j]%=mod;
                    }

    //这里可以多计算一行然后直接快乐输出。第n+1行不种植玉米等价于前n行种植玉米的情况
    cout<<f[n+1][0]<<endl;
    return 0;
}