洛谷1879 [USACO06NOV]Corn Fields

题意

在一个 $N\times M$ 的田地里种草，有的地方不能种，要求不能有两块相邻的。求方案数。

其中 $N,M\le 12$ 。

题解

状压dp。把图存下来，每次枚举时判断状态合不合法即可。

$$\text{f}[i][j]+=\text{f}[i-1][k]$$

#include<bits/stdc++.h>
#define ha 100000000

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,m,M,cnt,ans,f[15][5005],s[15],c[5005];

int main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) s[i]=(s[i]<<1)+read();
    M=1<<m;
    for (int i=0;i<M;i++)
    {
        if (i&(i<<1)) continue;
        c[++cnt]=i;
        if ((i&s[1])==i) f[1][cnt]=1;
    }
    for (int i=2;i<=n;i++)
    {
        for (int j=1;j<=cnt;j++)
        {
            if ((c[j]&s[i])!=c[j]) continue;
            for (int k=1;k<=cnt;k++)
            {
                if ((c[k]&s[i-1])!=c[k]) continue;
                if (c[j]&c[k]) continue;
                f[i][j]=(f[i][j]+f[i-1][k])%ha;
            }
        }
    }
    for (int i=1;i<=cnt;i++) ans=(ans+f[n][i])%ha;
    printf("%d",ans);
    return 0;
}