一开始根本不会状压dp，上网各种找题解，但发现他们写的都很......反正我作为一个没有接触过状态压缩的，根本看不懂！
然后看了好多状态压缩的题的题解，总结了一下思路，思路很重要，有了思路转换成计算机语言就好了。因此我先讲一下思路：
先说说地图，地图上每一行的01代表一个状态，比如输入样例中的111、010，表示第一行的三个位置都可以种稻子，第二行中间的位置可以种稻子，然后，不能种稻子的地方一定不能种稻子（废话...）
可以种稻子的地方可以选择种也可以选择不种，然后有一个前提条件，就是上下左右相邻的地方不能种稻子。
再说说怎么状态压缩，状态压缩就是把每一个状态压缩成二进制，二进制就是由01组成的，0代表不种，1代表种。二进制就要牵扯到位运算，位运算我就不想说了，百度吧。因此，一串01的二进制数就
可以代表一个状态，例如输入样例第一行是111，那么可以放入第一行的状态有，100、010、001、101、000，因为相邻位置不能放所以只有5种方法，那么第二行就只有2种方法000、010（不考虑其他行）
那么看第一行和第二行(第一行——第二行)，100——000，010——000，001——000，101——000，000——000，这是5种对应方法，还可以100——010，001——010，101——010，000——010这是另外的4种对应方法（第一行5种状态对吧?第二行2种状态，按照乘法原理，应该有5*2 = 10种方法，但是111——010是不合法的，因此样例的答案是10-1 = 9）。
dp[i][j]意思是推到第i行状态为j的方案总数。
那么“100——000”即为dp[2][000]可以由dp[1][100]得到,那么dp[2][000] = dp[2][000] + dp[1][100];
那么“010——000”即为dp[2][000]可以由dp[1][010]得到,那么dp[2][000] = dp[2][000] + dp[1][010];
......
以此类推，逐行递推。
总结一下思路：先枚举第一行，把所有可能的状态和第一行的地图对比，如果成功，则在循环里继续枚举第二行，把所有可能的状态和第二行的地图对比，如果成功，再和第一行填入的状态对比，如果又匹配成功，则dp[2][000] = dp[2][000] + dp[1][100];方法数加到第二行。这就是一次循环结束了，从新枚举第二行...
把思路转换成代码
can[]代表可行的状态，稍后解释。cur[i]代表地图的第i行
1 for(int i=;i<m;i++)//枚举每一行
{
for(int j=;j<tot;j++)//对第i行枚举所有可行的状态j
{
if((can[j]&cur[i])==)//如果状态j和第i行匹配了
{
for(int k=;k<tot;k++)//枚举第i+1行的所有可行的状态k
{
if(((can[k]&cur[i+])==)&&((can[k]&can[j])==))//状态k和第i+1行匹配且和状态j匹配
dp[i+][can[k]] = dp[i+][can[k]]+dp[i][can[j]];//状态数相加
}
}
}
}
这样核心代码就实现了。
有一个小方法，就是枚举可行状态的时候，假如一行是8列，不必从00000000枚举到11111111，这样很麻烦，所以要预处理。
就是在一开始把，一行的可行状态先求出来就拿“11111111”来说，这肯定是不可能的，因为有相邻的1，所以在一开始就可以舍弃掉。怎么做呢?
假如一行是8列，先从00000000枚举到11111111，对于每一个状态把它左移1位，再和他自己&运算，假如结果>0,就说明有有相邻的1，举个简单的例子：
01011要判断有没有相邻的1，if(((01011<<1) & (01011)） > 0 )则有相邻的1，(01011<<1) & (01011) 就是 01010和0101按位且运算，这两个红色地方1&1 == 1，因此结果大于0。
怎么实现呢?
tot = ;//全局变量，相当于栈的top,代表可行的状态数
for(int i=;i<(<<n);i++)//n是列数,i是枚举的状态
if((i&(i<<))==) can[tot++] = i;
dp[][]肯定要初始化对吧?不然全是0了，只要对第一行初始化就行了，因为后面的的行都是由第一行得来的
for(int i=;i<tot;i++)
if((cur[]&can[i])==) dp[][can[i]] = ;//和cur[1](第一行)匹配，就给对应的dp赋值为1
最后一步就是得到cur[]
for(int i=;i<=m;i++)
{
for(int j=;j<n;j++)
{
int num;
scanf("%d",&num);
if(num==) cur[i] = (cur[i]|(<<j));//这里要给0的地方变为1,1的地方放上0,因为要保证不合法的匹配一定是独一无二的。自己思考一下吧
}
}
最后贴一下完整代码，一开始学的时候，感觉主流代码都一模一样，而且一大堆乱七八糟的函数，麻烦又看不懂，于是下定决心如果自己搞明白了，一定要写一个大家都看得懂的题解，感觉自己讲的比其他都清楚了，如果看不懂就真没办法了......
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 100000000 using namespace std;
int dp[][<<],cur[];
int can[<<],tot,m,n; int main()
{
while(~scanf("%d%d",&m,&n))
{
tot = ;
for(int i=;i<(<<n);i++)
if((i&(i<<))==) can[tot++] = i;
memset(cur,,sizeof(cur));
memset(dp,,sizeof(dp));
for(int i=;i<=m;i++)
{
for(int j=;j<n;j++)
{
int num;
scanf("%d",&num);
if(num==) cur[i] = (cur[i]|(<<j));
}
}
for(int i=;i<tot;i++)
if((cur[]&can[i])==) dp[][can[i]] = ;
for(int i=;i<m;i++)
{
for(int j=;j<tot;j++)
{
if((can[j]&cur[i])==)
{
for(int k=;k<tot;k++)
{
if(((can[k]&cur[i+])==)&&((can[k]&can[j])==))
dp[i+][can[k]] = dp[i+][can[k]]+dp[i][can[j]];
}
}
}
}
int ans = ;
for(int i=;i<tot;i++)
{
ans += dp[m][can[i]];
ans = ans % mod;
}
printf("%d\n",ans);
}
}