【poj3254】Corn Fields題意＆題解＆代碼（C++）
題目鏈接：
http://poj.org/problem?id=3254
題意：
給出一個n行m列的草地，1表示肥沃，0表示貧瘠，現在要把任意數量牛放在肥沃的草地上，但是要求所有牛不能相鄰，問有多少種放法。
題解：
狀態壓縮型dp，一般可以通過數據范圍來判斷，我們可以將每一行的肥沃草地狀態與牛的分布狀態用二進制數來表示出來，dp[i][j]表示在第ｉ行牛的狀態為ｊ的方法數，轉移方法見代碼，而且我們發現題上要求兩個牛不能相鄰，那麼在二進制狀態種有很多的狀態都不滿足這一性質，原本２^ｍ種狀態經過預處理後發現實際上滿足的限制的狀態數很少，可以自己寫個小程序算一下最多有多少種。
代碼：
#include
#include
#include
using namespace std;
int ans,n,m,dp[13][1<<13],map[13],st[1<<13];
int M=1e8;
int judge1(int x)//判斷此狀態是否有相鄰的牛
{
return x&(x<<1);
}
int judge2(int i,int x)//判斷此狀態與地圖是否沖突
{
return map[i]&x;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
int x;
scanf("%d",&x);
if (x==0) map[i]+=(1<<(j-1));
}
int tot=0;
for (int i=0;i<=(1<
