POJ - 3254 Corn Fields

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.

       基础的状压dp学习开始~~（没办法队里只有我学dp，两个懒汉QAQ）~

       dp[i][j]来表示第i行状态为j的时候的状态数量有多少~~ mp[i]表示i这行的是否允许放置的状态（二进制表示），这样的话在i行的时候j状态能否行驶的判断是由他自己是否存在两个紧邻的1（b&(b<<1)）以及是否满足mp[i]的放置规则((b&mp[a])==b)。然后若i行j状态能够放置，那么对k进行从0到（1<<m）的循环，判断是否k与j是否存在紧邻的1（k&j）如果可以防置，那么dp[i][j]=dp[i][j]+dp[i-1][k];

       别忘了初始化的时候dp[0][0]=1;

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int mod = 100000000;
#define ll long long int
int mp[15];
int dp[15][1 << 15];
int n, m;
void init() {
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		int ans = 0;
		for (int j = 0; j < m; j++) {
			int t; scanf("%d", &t);
			ans = (ans << 1) + t;
		}
		mp[i] = ans;
	}
}
bool judge(int a,int b) {
	if ((b&mp[a])!=b)return 0;//1010   1110
	if (b&(b << 1))return 0;
	return 1;
}
int main() {
	while (~scanf("%d%d", &n, &m)) {
		init();
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < (1 << m); j++) {
				if (!judge(i, j))continue;
				for (int k = 0; k < (1 << m); k++) {
					if (j&k)continue;
					dp[i][j] += dp[i - 1][k];
					dp[i][j] %= mod;
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < (1 << m); i++) {
			ans += dp[n][i];
			ans %= mod;
		}
		cout << ans << '\n';
	}
}