题解 | 小心火烛的歪

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
//用回溯+剪枝的方式遍历所有可能性，并在递归过程中维护最优解
//棋盘数据和计划都用一个long数据存放方便位运算，每一格棋盘就是二进制的一位
public class Main {
    static int size;//空格数量
    static int bastSelect;//最优选择，如4个计划选择1和3时，则是二进制1010
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) { 
            int n=in.nextInt();
            int m=in.nextInt();
            int q=in.nextInt();
            size=n*m;
            bastSelect=-1;//初始-1会将所有为置为1，相当于默认最大值
            in.nextLine();
		  //初始化草地，用二进制每一位代表一个格子
            long board=0L;
            for(int i=0;i<n;i++){
                board<<=m;
                board|=Integer.valueOf(in.nextLine(),2);
            }
		  //初始化所以计划，同样每个计划二进制存放
            long[] plan=new long[q];
            for(int i=0;i<q;i++){
                long temp=0L;
                for(int j=0;j<n;j++){
                    temp<<=m;//空出m位存放下一行数据
                    temp|=Integer.valueOf(in.nextLine(),2);
                }
                plan[i]=temp;
            }
            backtrack(0,plan,board,0,board);
            if(bastSelect==-1){
			  //未修改最优选择则表示所有计划无法覆盖题目要求
                System.out.println(-1);
            }else{
                System.out.println(Integer.bitCount(bastSelect));
                int idx=1;
                while(bastSelect>0){
                    if((bastSelect&1)==1){
                        System.out.print(idx+" ");
                    }
                    bastSelect>>=1;
                    idx++;
                }
            }    
        }
    }
  //idx:plan的索引
  //plan:计划集合
  //cur:二进制存储当前棋盘情况，0的位置表示闲置需要放烟花，1的位置表示已经放了杂物或者烟花
  //select:存储已选择计划情况
  //board：杂物位置
    public static void backtrack(int idx,long[] plan,long cur,int select,long board){
	  //1L<<(size))-1表示当前棋盘长度的二进制串，全是1则表示cur已放满烟花
        if(cur==(1L<<(size))-1){
            bastSelect=select;
            return;
        }
        if(idx==plan.length)return;
	  //提前剪枝，当前select计划数等于或者超过最优则无需继续计算
        if(Integer.bitCount(select)>=Integer.bitCount(bastSelect))return;
        //idx计划的烟花放到了杂物位置，不合要求所以直接跳过该计划
        if((plan[idx]&board)!=0){
            backtrack(idx+1,plan,cur,select,board);
            return;
        }
        //选择idx计划
        backtrack(idx+1,plan,cur|plan[idx],select|(1<<idx),board);

        //不选idx计划
        backtrack(idx+1,plan,cur,select,board);
    }
}