poj 3254 Corn Fields（状态压缩dp）

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

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.```

Source

USACO 2006 November Gold

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 #define N 16
6 #define M 1<<N
7 #define MOD 100000000
8 int mp[M];//记录每一行中，不能种植的就将状态记为1
9 int state[M];//记录1<<m中不与别的数相邻的所有状态
10 int dp[N][M];
11 bool judge(int x){
12     return x&(x<<1);
13 }
14 bool judge2(int i,int j){
15     return mp[i]&state[j];
16 }
17 int main()
18 {
19     int n,m;
20     while(scanf("%d%d",&n,&m)==2){
21
22         memset(mp,0,sizeof(mp));
23         memset(state,0,sizeof(state));
24         memset(dp,0,sizeof(dp));
25
26         for(int i=1;i<=n;i++){
27             for(int j=1;j<=m;j++){
28                 int x;
29                 scanf("%d",&x);
30                 if(x==0){
31                     mp[i]+=(1<<(j-1));
32                 }
33             }
34         }
35
36         int k=0;
37         for(int i=0;i<(1<<m);i++){
38             if(judge(i)==0){
39                 state[k++]=i;
40             }
41         }
42
43         for(int i=0;i<k;i++){
44             if(judge2(1,i)==0){
45                 dp[1][i]=1;
46             }
47         }
48
49         for(int i=2;i<=n;i++){
50             for(int j=0;j<k;j++){
51                 if(judge2(i,j)) continue;
52                 for(int l=0;l<k;l++){
53                     if(judge2(i-1,l)) continue;
54                     if((state[j]&state[l])==0){
55                         dp[i][j]+=dp[i-1][l];
56                     }
57                 }
58             }
59         }
60         int ans=0;
61         for(int i=0;i<k;i++){
62             ans=ans+dp[n][i];
63             ans%=MOD;
64         }
65         printf("%d\n",ans);
66     }
67     return 0;
68 }```

POJ 3254 Corn Fields 状态压缩DP （C++/Java）

http://poj.org/problem?id=3254 题目大意: 一个农民有n行m列的地方,每个格子用1代表可以种草地,而0不可以.放牛只能在有草地的,但是相邻的草地不能同时放牛, 问总共有多少种方法. 思路: 状态压缩的DP. 可以用二进制数字来表示放牧情况并判断该状态是否满足条件. 这题的限制条件有两个: 1.草地限制. 2.相邻限制. 对于草地限制,因为输入的时候1是可以种草地的. 以"11110"草地分析,就只有最后一个是不可以种草的.取反后得00001  .(为啥取反

POJ 3254 Corn Fields(状态压缩DP）

Corn Fields Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 4739   Accepted: 2506 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 yumm

POJ 3254. Corn Fields 状态压缩DP (入门级)

Corn Fields Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 9806   Accepted: 5185 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 yumm

[ACM] POJ 3254 Corn Fields(状态压缩）

Corn Fields Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 8062   Accepted: 4295 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 yumm

poj - 3254 Corn Fields (状态压缩入门)

http://poj.org/problem?id=3254 参考:http://blog.csdn.net/accry/article/details/6607703 农夫想在m*n的土地上种玉米,但是有的土地很贫瘠,所以不能种,每块土地标为1的表示能种,标为0的表示不能种,并且种玉米的土地不能相邻, 问有多少种合法的种植方案.(全部不种也算一种) 第一道状压,理解了比较久的时间. 就是用二进制的0和1代表土地种还是不种,这样每一行都可以用一个2进制数表示,列数<=12,故最多有2<<

Poj 3254 Corn Fields(状态压缩)

Corn Fields Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 8291   Accepted: 4409 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 yumm