题解 | 小心火烛的歪

import java.util.*;

public class Main {
    static int M = 10;
    static int n, m, p, cnt = M, res;
    static StringBuilder cd = new StringBuilder();
    static BitSet cdBit = new BitSet();
    static StringBuilder[] jh = new StringBuilder[M];
    static BitSet jhAll = new BitSet();
    static BitSet[] jhBit = new BitSet[M];
    static boolean[] vis = new boolean[M];
    // 输入
    static void input() {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        p = in.nextInt();
        in.nextLine(); // 读取残留的换行符
        for (int i = 0; i < n; i++) {
            String str = in.nextLine();
            cd.append(str);
        }
        for (int i = 0; i < cd.length(); i++) {
            if (cd.charAt(i) == '1') {
                cdBit.set(i);
            }
        }
        for (int i = 0; i < p; i++) {
            jh[i] = new StringBuilder();
            jhBit[i] = new BitSet();
            for (int j = 0; j < n; j++) {
                String str = in.nextLine();
                jh[i].append(str);
            }
            for (int j = 0; j < jh[i].length(); j++) {
                if (jh[i].charAt(j) == '1') {
                    jhBit[i].set(j);
                }
            }
        }
    }
    // 输出
    static void print(int x) {
        if (cnt == M) {
            System.out.println(-1);
            return;
        }
        System.out.println(cnt);
        int cnt = 0;
        while (x > 0) {
            cnt++;
            if ((x & 1) == 1) {
                System.out.printf("%d ", cnt);
            }
            x >>= 1;
        }
    }

    static boolean isSuit(BitSet a, BitSet b) {
        BitSet tmpb = (BitSet) b.clone();
        tmpb.flip(0, n * m); // 注意长度
        if (a.equals(tmpb)) {
            return true;
        }
        return false;
    }

    static int get1Num(int x) {
        int cntX = 0;
        while (x > 0) {
            if ((x & 1) == 1) {
                cntX++;
            }
            x >>= 1;
        }
        return cntX;
    }

    static void calc(BitSet a, BitSet b, int x) {
        if (isSuit(a, b)) {
            int num = get1Num(x);
            if (cnt > num) {
                cnt = num;
                res = x; // 记录状态
            }
        }
    }

    static void dfs(int num, int now) {
        if (now > num) {
            int result = 0, pow = 1;
            for (int i = 0; i < p; i++) {
                if (vis[i]) {
                    result += pow;
                }
                pow <<= 1;
            }
            calc(cdBit, jhAll, result);
            return;
        }
        for (int i = 0; i < p; i++) {
            if (!vis[i]) {
                BitSet tmpJhAll = (BitSet)jhAll.clone();
                jhAll.or(jhBit[i]);
                vis[i] = true;
                dfs(num, now + 1);
                vis[i] = false;
                jhAll = tmpJhAll;
            }
        }
    }

    public static void main(String[] args) {
        input();
        // 选出其中的部分计划，进行或运算
        // 方法1：状压
        // for (int i = 0; i < (1 << p); i++) {
        //     jhAll.clear();
        //     for (int j = 0; j < p; j++) {
        //         if (((i >> j) & 1) == 1) {
        //             jhAll.or(jhBit[j]);
        //         }
        //     }
        //     calc(cdBit, jhAll, i);
        // }
        // 方法2：DFS
        for (int i = 0; i <= p; i++) {
            dfs(i, 1);
        }
        print(res);
    }
}

方法1：BitMap位运算+壮压的思想

方法2：BitMap位运算+DFS