?

题目大意：

一个农民有n行m列的地方，每个格子用1代表可以种草地，而0不可以。放牛只能在有草地的，但是相邻的草地不能同时放牛， 问总共有多少种方法。

思路：

状态压缩的DP。

可以用二进制数字来表示放牧情况并判断该状态是否满足条件。

这题的限制条件有两个：

1.草地限制。

2.相邻限制。

?

对于草地限制，因为输入的时候1是可以种草地的。

以”11110“草地分析，就只有最后一个是不可以种草的。取反后得00001 。（为啥取反？不取反可以举出反例的）

假设有个状态10101 这个不相邻，但是10101 & 00001 ！=0 表示有冲突。

?

对于相邻限制，又分为同一行的限制和上下两行的限制。

同一行限制可以一开始把相邻的情况都去掉，符合的存进数组，有助于减少状态数。 这样这个也解决了。

上下两行相与即可。

如（假设均可种草）

10101 & 00100！=0 也是有冲突的。

?

OK上代码。

?

C++：

?

#include
  
   
#include
   
     const int mod = 100000000; const int MAXN = 1 << 12; int map[20], status[MAXN], dp[20][MAXN]; int len; int main() { int n, m; while (~scanf(%d%d, &n, &m)) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int temp; scanf(%d, &temp); if (!temp) map[i] = map[i] | (1 << (m - j - 1)); } } len = 0; int tot = 1 << m; //所有状态 for (int i = 0; i < tot; i++) { //左移右移均可 if ((i &(i >> 1)) == 0) status[len++] = i; } //初始化第一行 memset(dp, 0, sizeof(dp)); for (int i = 0; i 
    
     
?
     
?
     
?
     
?
     
JAVA:
     
import java.util.Scanner;

public class Main {

	final static int mod = 100000000;
	final static int MAXN = 1 << 12;
	static int[] map = new int[20];
	static int[] status = new int[MAXN];
	static int[][] dp = new int[20][MAXN];
	static int len;

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int n, m;
		while (cin.hasNext()) {
			n = cin.nextInt();
			m = cin.nextInt();
			init(n,m);

			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++) {
					int temp = cin.nextInt();
					if (temp ==0)
						map[i] = (map[i] | (1 << (m - j - 1)));
				}

			int tot = 1 << m;
			len = 0;
			for (int i = 0; i < tot; i++)
				if ((i & (i << 1)) == 0) {
					status[len++] = i;
				}

			for (int i = 0; i < len; i++) {
				if ((map[0] & status[i]) == 0)
					dp[0][i] = 1;
			}

			for (int i = 1; i < n; i++) {
				for (int j = 0; j < len; j++) {
					if ((map[i - 1] & status[j]) != 0)
						continue;
					for (int k = 0; k < len; k++) {
						if ((map[i] & status[k]) != 0)
							continue;
						if ((status[j] & status[k]) != 0)
							continue;
						dp[i][k] = (dp[i][k] + dp[i - 1][j]) % mod;
					}
				}
			}
			int ans = 0;
			for (int i = 0; i < len; i++) {
				ans = (ans + dp[n - 1][i]) % mod;
			}
			System.out.println(ans);
		}
	}

	public static void init(int n,int m)
	{
		int tot=1<