Problem 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

題意：給出一個大小為 n*m 的地，1 可以種植，0 不可以種植，兩株植物不能相鄰種植，求所有種植方法數，并取模 100000000

思路：狀壓 DP 入門題

每一行的情況就可通過一個二進制數 state 來存儲，其范圍是：0 ~ 1<< state，用?dp[i][state] 來表示第 i 行狀態為 state 的情況下滿足條件的數目，則狀態轉移方程為：dp[i][state] += dp[i-1][pre_state]，且?state 和 pre_state 必須滿足所給條件，即左右上下均不相鄰，答案為最后一行所有狀態的情況相加。

Source Program

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<map> #include<stack> #include<ctime> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 100000000 #define E 1e-6 #define LL long long using namespace std; int n,m; int a[15][15]; int dp[15][1<<15];bool check(int x,int state) {if(state&(state<<1))return false;for(int i=1;i<=m;i++)if(!a[x][i])if( (1<<(m-i)&state)!=0 )return false;return true; }int main() {while(scanf("%d%d",&n,&m)!=EOF){memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];dp[0][0]=1;LL res=0;for(int i=1;i<=n;i++){for(int j=0;j<(1<<m);j++){if(check(i,j))//判斷當前行滿足條件的state{for(int k=0;k<(1<<m);k++)//枚舉上一行的pre_state進行更新{if(!(k&j))dp[i][j]+=dp[i-1][k];}if(i==n)res=(res+dp[i][j]) % MOD;}}}printf("%lld\n",res);}return 0; }

?

總結

以上是生活随笔為你收集整理的Corn Fields（POJ-3254）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。