Crawling in process... Crawling failed Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
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
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
Sample Input
2 3
1 1 1
0 1 0
Sample Output
9
Hint
1 2 3
4
There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.
/*
poj3254
分类：状压DP
因为后一行的状态只与前一行有关，考虑使用DP做
每一行最多有12个格子，用0表示不取，1表示取总共有1<<12-1种情况
首先单独看某一行，合法的状态是没有两个1彼此相邻，用位运算来判断
i&(i<<1)为0则表示没有相邻的1，是合法状态。
先初始化出所有的不考虑某块地不能选择的情况，保存所有的合法状态，
然后再结合题目进行筛选，筛选范围时1~(1<<m),看那种合法状态是否
与草原实际相符，具体办法就是依次取合法状态的某一位，如果改位为
1但实际上这块草地不能取，这种状态就是不可行的，第一行若第j种状态可行
dp[i][j]=1，状态转移方程则是dp[i][j]+=dp[i-1][k],k代表上一层的可行状态
若不可行，dp[i-1][k]=0,所以初始化时要将dp数组初始化为0
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=(<<);//最多有12列
int v[maxn],dp[][maxn];
int a[][];//用来存图；
int n,m;
const long long mod=;
int tot;
void init()
{
tot=;
for(int i=;i<maxn;i++)//记录所有合法状态
{
if((i&(i<<))==)
v[tot++]=i;
}
}
bool check(int row,int p)
{
for(int i=;i<=m;i++)
{
if((p&(<<(i-)))&&!a[row][i])//这种状态不符合实际
return true;
}
return false;
}
int main()
{
init();
// for(int i=0;i<tot;i++)
// cout<<v[i]<<" ";
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=;i<=n;i++)
{
for(int j=;v[j]<(<<m);j++)
{
if(check(i,v[j])) continue;
if(i==)
{
dp[i][j]=;
continue;
}
for(int k=;v[k]<(<<m);k++)
{
if((v[j]&v[k])==)
dp[i][j]+=dp[i-][k];
}
}
}
__int64 ans=;
for(int i=;v[i]<(<<m);i++)
{
ans=(ans+dp[n][i])%mod;
}
printf("%I64d\n",ans);
}
}