Description
Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.
Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.
Input
Line 1: Two space-separated integers: M and N
Lines 2.. M+1: Line i+1 describes row i of the pasture with N space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)
Output
Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000.
Sample Input
2 3
1 1 1
0 1 0
Sample Output
9
Hint
Number the squares as follows:
1 2 3
4
题意：农夫有一块地，被划分为m行n列大小相等的格子，其中一些格子是可以放牧的（用1标记），农夫可以在这些格子里放牛，其他格子则不能放牛（用0标记），并且要求不可以使相邻格子都有牛。现在输入数据给出这块地的大小及可否放牧的情况，求该农夫有多少种放牧方案可以选择（注意：任何格子都不放也是一种选择，不要忘记考虑！
解题思路：虽然是个入门题，但是对于本菜鸡还是啃了好久，题解很多地方都找的到，在这里就说一些本人觉得重要的事吧
1.状态压缩，这题怎么压缩了？---把每一行的各种情况抽象成二进制，0代表放，1代表不放。例如;101代表第一个，第三个位置放置。
2.如何判断总共有多少种放置方法？---对于某一种方法x,将其左移一位做按位与运算，如果有相邻，返回值一定不是零，那么就可以判断了。如x=6(十进制） 对应 110（二进制）左移后变为100，与运算为100 非0，那么就是相邻。
3.上述只是判断了当给定列数的时候可以有多少种不相邻的方案（即每一列都能放），可是真实的每一个行都是有限制放置个数，那么该怎么办呢？关键在于下面代码给出的isok函数，我们在输入当前行列状态时设置一个mp[i]函数，记录每一行的输入情况，将0置为1,1置为0，如第一行输入为1001，我们储存则储存为0110，那么把对应的上述得到的数和各种方法做与运算，如果返回的是空值--说明可行，因为只有在不能种玉米的地方填入1了，与mp【i】与的结果才会返回非0；
4.接下来就是一行一行的dp，最终把dp【n】【k】相加即可。
通过对样例数据的分析即可以发现不同状态之间的关系：
以dp[i][state(j)]来表示对于前i行，第i行采用第j种状态时可以得到的可行方案总数！
例如：回头看样例数据，dp[2][1]即代表第二行使用第2中状态（0 1 0）时可得的方案数，即为4；
那么，可得出状态转移方程为：
dp[i][state(j)]=dp[i-1][state(k1)]+dp[i-1][state(k2)]+......+dp[i-1][state(kn)](kn即为上一行可行状态的编号，上一行共有n种可行状态）
最终ans=dp[m][state(k1)]+dp[m][state(k2)]+......+dp[m][state(kn)]; (kn即为最后一行（第m行）可行状态的编号）
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 13;
const int mod = 100000000;
const int ted = 1<<13;
int st[ted];//保存可以使用的“行”的格式
int mp[ted];//保存地图每一列
int dp[maxn][ted];
int judge(int x)//判断是否有相邻的1
{return (x&x<<1);//这步很巧妙 错开一位 如果都是相邻为0 这个操作返回0
}
int isok(int i,int j)//判断能不能放的下
{return (mp[i]&st[j]);//判断地i行地图和第j种方法（如果返回非0代表上下有相邻的1)
}
int n,m,x;
int main()
{cin>>n>>m;memset(dp,0,sizeof(dp));memset(st,0,sizeof(st));memset(mp,0,sizeof(mp));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>x;if(x==0)mp[i]+=(1<<(m-j));//开始进行状态排列}}int k=0;for(int i=0;i<(1<<m);i++){if(!judge(i))//如果i状态没有相邻的1 st[k++]=i;//记录每一行可以采用的状态 }for(int i=0;i<k;i++){if(!isok(1,i))//先和第一行对比一下dp[1][i]=1;}for(int i=2;i<=n;i++){for(int j=0;j<k;j++){if(isok(i,j))//如果出现上下相邻continue;for(int t=0;t<k;t++){if(isok(i-1,t))//摆放之前先对状态'T'进行一下判断continue;if(!(st[t]&st[j]))dp[i][j]+=dp[i-1][t];}}}int ans=0;for(int i=0;i<k;i++){ans=(ans+dp[n][i])%mod;}printf("%d\n",ans);return 0;
}