题意：Farmer John 放牧cow，有些草地上的草是不能吃的，用0表示，然后规定两头牛不能相邻放牧。问你有多少种放牧方法。
状态压缩dp其实就是用二进制来表示所有的状态，比如这题， 我们在某一行可以这样取0 1 0 1 1 0 1，用1代表取了，0代表没取，因为这点，它的数据量也限制在20以内，所有看到这样数据量的题目可以先考虑一下状态压缩dp。对于有多行的数据，所有状态的总数必然很庞大，而且不用特殊的方法想要存储这些状态是不太现实的。既然每个点只有这两种情况，我们可以用二进制的一位来表示，0 1 0 1 1 0 1就可以表示为二进制0101101也就是十进制的45，如果我们想要枚举6个点的所有状态，我们只需要从0到2^6取其二进制就可以了，并不会重复或是多余。
然后关于这题，题目要求不相邻，也就是说每个状态中不能有两个1相邻，代码中我用了checkself()函数判断。还有，有些地方是非法的，我在输入的时候将非法的状态保存了，一行只占一个整数，只需要判断某状态中只要有个一位和非法状态总的一位都为1，这个状态必然非法，这里我用了check()函数。
我们检测完了状态的合法性，接下来就是状态转移的问题了。对于当前行的合法状态，到这个状态的方法数目一定是前一行与它不冲突（也就是没有行之间相邻的点）的方法数之和（记得mod）。这样求出到最后一行所有状态的方法数，求其和，然后取余，这就是我们要的结果。
#include <stdio.h>
#include <string.h>
#define MOD 100000000
#define maxn 13
int dp[maxn][1<<maxn]; //每个状态可以放牧方法的总数
int n, m;
int sta[maxn]; //能不能放牧的状态
bool check(int x, int y) //检查同列有没有相邻的或者x的状态是否可以存在
{
if (x&y)
return false;
return true;
}
bool checkself(int x) //检查同行有没有相邻的
{
if (x&(x<<1))
return false;
return true;
}
int getresult()
{
int num = 1<<m;
for (int i = 0; i < num; i++)
{
if (check(i, sta[1]) && checkself(i))
dp[1][i] = 1;
}
for (int i = 2; i <= n; i++)
{
for (int j = 0; j < num; j++)
{
if (!check(j, sta[i])) //sta[i]表示i行不能存在的状态
continue;
for (int k = 0; k < num; k++)
{
if (check(k, j) && checkself(j) && checkself(k))
dp[i][j] += (dp[i-1][k]%MOD);
}
}
}
int ans = 0;
for (int i = 0; i < num; i++)
{
ans += (dp[n][i]%MOD);
}
return ans%MOD;
}
int main()
{
int t;
while (scanf("%d %d", &n, &m) != EOF)
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &t);
if (!t)
{
sta[i] += (1<<(m-j)); //这里对不能出现的状态做标记
}
}
}
printf("%d\n", getresult());
}
return 0;
}
