一个月之后修改

一个月之后再次看到这个题，发现其实并没有那么难，其实主要将check内容搞定，也就是st数组搞定，就可以做状态转移了。

心得

我太菜了，最无语的地方就是耗一晚上理解了算法，又耗一早晨才把JAVA写出来😓而且比CPP冗长很多。。
大概我个人认为需要注意的点有以下：

1. f[i][j]的意义，表示i-1列已经摆好，且从i - 1申到i的状态为j，的所有方案
2. 对于转移方程，f[i][j]之后会对于j继续分配，但前提是上一层状态k已经固定，那么需要满足的是
   (1). j & k 没有交集 (2) j｜k 中间不能有奇数个，并且！！结尾也不能有奇数个（容易想不到）
3. 对于j | k 可以开始的时候判断状态，将状态存在st[]的boolean数组中(st means status)，需要在开始的时候便利
4. f[0][0]为1(base case必须要有），因为从-1申到0的方案只有一种，就是没有申。。
5. 所求为f[m][0]，即为前m - 1列都已经排好，且申到m列的数量为0；因为是从0开始排的，i因为0，0已有，所以从1开始，j是从0开始排，而之前的 0 - m -1 即为m列。m作为边界便可以求出了。
6. 任何n*m的矩阵，都是按照 row * column来排列的，所以n对应的就是row

以下是JAVA代码中易错的点

1. 关于Scanner的运用，因为该题的设定是当输入为0 0时，Scanner会跳出，此处有两个方法可以完成
   分别是hasNextInt() 和 while(true);而因为每输入两个数完然后return，所以会被判定已经输入结束，所以hasNextInt()不能用，只能用while(true),然后当n，m = 0，跳出循环。这一点和C在while中的直接操作有所不同，(C是真的好用啊。JAVA写的👴好心累。)
2. 关于JAVA中，不能while中直接写if (i >> j & 1),并且因为优先级 & 低于 ==， if (i >> j & 1 == 1)，会被报错，所以要为if ((i >> j & 1) == 1)
3. 每次要重置f,需要手动重置，遍历一遍数组

Java 代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = 12, M = 1 << N;
        boolean[] st = new boolean[M];
        long[][] f = new long[N][M];

        //先计算任意一个数的空白存在情况，为j | k来做准备
        while (true) {
        //当m,n=0是跳出true的循环
            int n = sc.nextInt();
            int m = sc.nextInt();
            if (m == 0 && n == 0) break;
                for (int i = 0; i < 1 << n; i++) {
                    int count = 0;
                    st[i] = true;
                    for (int j = 0; j < n; j++) {
                        if (i >> j & 1 == 1) {
                            if ((count & 1) == 1) {
                                st[i] = false;
                            }
                            count = 0;
                        } else {
                            count++;
                        }
                    }
                    if ((count & 1) == 1) st[i] = false;//最后的count也需要计算，这个容易忘
                }
                //重置
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        f[i][j] = 0;
                    }
                }

                f[0][0] = 1;//base case很重要
                for (int i = 1; i <= m; i++) {
                    for (int j = 0; j < 1 << n; j++) {
                        for (int k = 0; k < 1 << n; k++) {
                            if (st[(j | k)] == true && (j & k) == 0 ) {
                                f[i][j] += f[i - 1][k];
                            }
                        }
                    }
                }
            System.out.println(f[m][0]);
        }
    }
}

大家冲冲冲!