算法分析

注意：题目中还有着哪些坑不能种玉米，需要特殊标记一下，w[i]记录的是第i行能不能种玉米的状态，w[i]的二进制表示中，某位是1表示该位置不能填坑，0表示该位置可以填坑，当枚举到当前状态state时，若state & w[i] == 0表示合法

时间复杂度

上限复杂度是$O(n * s * k)$，n表示行数，s表示合法状态数量，k表示合法状态的转移数量

参考文献

算法提高课

Java 代码

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N = 14,M = 1 << N ;
    static int[] w = new int[N];
    static int n,m;
    static ArrayList<Integer> state = new ArrayList<Integer>();
    static ArrayList<Integer>[] head = new ArrayList[M];
    static int[][] f = new int[N][M];
    static int mod = 100000000;
    static boolean check(int s)
    {
        for(int i = 0;i < m;i ++)
        {
            if((s >> i & 1) == 1 && (s >> i + 1 & 1) == 1)
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 1;i <= n;i ++)
        {
            int t = 0;
            for(int j = 0;j < m;j ++)
            {
                int x = scan.nextInt();
                if(x == 0) t += 1 << j;
            }
            w[i] = t;
        }

        //预处理出相邻的不能为1的状态
        for(int i = 0;i < 1 << m;i ++)
        {
            if(check(i))
                state.add(i);
        }

        //判断哪些状态和哪些状态可以搭配
        for(int i = 0;i < state.size();i ++)
        {
            head[i] = new ArrayList<Integer>();
            for(int j = 0;j < state.size();j ++)
            {
                int a = state.get(i);
                int b = state.get(j);
                if((a & b) == 0)
                    head[i].add(j);
            }
        }

        f[0][0] = 1;
        for(int i = 1;i <= n;i ++)
        {
            for(int a = 0;a < state.size();a ++)
            {
                if((state.get(a) & w[i]) == 0)
                    for(int b : head[a])
                    {
                        f[i][a] = (f[i][a] + f[i - 1][b]) % mod;
                    }
            }
        }
        long res = 0;
        for(int i = 0;i < 1 << m;i ++) res = (res + f[n][i]) % mod;
        System.out.println(res);

    }
}