$$\color{Red}{从蒙德里安 ——> 小国王 ——> 玉米田 逐层分析}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

农夫约翰的土地由 M×N 个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式

第 1 行包含两个整数 M 和 N

第 2..M+1行：每行包含 N 个整数 0 或 1，用来描述整个土地的状况，1表示该块土地肥沃，0表示该块土地不育。

输出格式
输出总种植方法对 1e8 取模后的值。

数据范围

1≤M,N≤12

输入样例：

2 3
1 1 1
0 1 0

输出样例：

9

思考

这道题可以看作小国王的缩减版，也是棋盘状压dp，只是从正方形变成矩形

而小国王的思想极其类似蒙德里安的梦想，关于这道题我有不下于千字的讲解，大家可以去看看，包括很多细节和边界条件的阐述

传送门：我的蒙德里安的题解

传送门：我的小国王题解

我们发现这题也是棋盘类的状态压缩状态，第 i行的状态和前一行后一行都有关联，所以不妨我们就从上到下去枚举状态，这样考虑第i行的状态只需要考虑第i - 1行的状态

那么我们的动态规划就可以这么来看f[i][j]---> 前i行状态为j的总方案数量

再来说明一下一个状态如何才算合法

    static boolean check(int state) {
        for (int i = 0; i < m; i++) {
            if ((state >> i & 1) == 1 && (state >> i + 1 & 1) == 1) {
                return false;
            }
        }
        return true;
    }

需要满足一行没有相邻的1才行，为什么这道题没有考虑领边取或运算的计算？
小国王和我们蒙德里安部分的分析相同，它的影响范围是口字形，一个地方为1，会影响邻边的对角线位置元素也不能为1，当满足 (a & b) == 0 即两行没有交集算第一个合法条件，同时此时求a | b,代表两个状态求并集，这个理由在蒙德里安讲过，此时也需要满足并集状态也没有相邻的1

这道题影响范围是十字形，只对领边相同位置有影响 因此只需要满足 (a & b) == 0 即可

我们的状态转移根据闫式dp分析法，可以这么考虑，当前的状态只能是合法的前一行(i - 1)的状态为b，各种合法相邻的情况的求和才行

为什么最后多了一维遍历，答案是f[n+1][0]?
答案本来按我们原定想法是从最后一行f[i][]循环找到底答案是状态为什么，可以利用遍历states，但是我们为什么多开一维的状态方程——》因为我们可以利用多计算一行的状态方程,此时n + 1行，并且状态为0，即没有一块田被种植，就是前n行合法的全部方案数

JAVA代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int N = 14, M = 1 << 12, mod = (int)1e8;
    static int[][] f = new int[N][M];
    static int n, m;
    static List<Integer> states = new ArrayList<>();
    static ArrayList<Integer>[] head = new ArrayList[M];
    static int[] g = new int[N];

    static boolean check(int state) {
        for (int i = 0; i < m; i++) {
            if ((state >> i & 1) == 1 && (state >> i + 1 & 1) == 1)
                return false;
        }
        return true;
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        //输入各行的状态，把不能种的地方设置为1，这样后面方便做与运算看是否后面的状态合法
        for (int i = 1; i <= n; i++) {
            String[] s2 = br.readLine().split(" ");
            for (int j = m - 1; j >= 0; j--) {
                int x = Integer.parseInt(s2[j]);
                g[i] += (x ^ 1) << j;
            }
        }
        //和小国王相同，把合法状态收集
        for (int i = 0; i < 1 << m; i++) {
            if (check(i))
                states.add(i);
        }
        //收集能和合法状态互相转化的头或尾
        for (int i = 0; i < states.size(); i++)
            for (int j = 0; j < states.size(); j++) {
                int a = states.get(i);
                int b = states.get(j);
                if ((a & b) == 0) {
                    if (head[i] == null)
                        head[i] = new ArrayList<>();
                    head[i].add(j);
                }
            }
        //赋初值
        f[0][0] = 1;
        //动态规划
        for (int i = 1; i <= n + 1; i++) {
            for (int j = 0; j < states.size(); j++) {
                if ((states.get(j) & g[i]) == 0){
                    for (int b : head[j]) {
                        f[i][j] = (f[i][j] + f[i-1][b]) % mod;
                    }
                }
            }
        }
        System.out.println(f[n+1][0]);
    }
}