小心火烛的歪

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	
	// Read first line: n, m, q
	scanner.Scan()
	firstLine := strings.Split(scanner.Text(), " ")
	n, _ := strconv.Atoi(firstLine[0])
	m, _ := strconv.Atoi(firstLine[1])
	q, _ := strconv.Atoi(firstLine[2])
	
	// Read initial state
	initialState := make([][]int, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		line := scanner.Text()
		initialState[i] = make([]int, m)
		for j := 0; j < m; j++ {
			initialState[i][j] = int(line[j] - '0')
		}
	}
	
	// Read plans
	plans := make([][][]int, q)
	for planIdx := 0; planIdx < q; planIdx++ {
		plans[planIdx] = make([][]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			line := scanner.Text()
			plans[planIdx][i] = make([]int, m)
			for j := 0; j < m; j++ {
				plans[planIdx][i][j] = int(line[j] - '0')
			}
		}
	}
	
	// Try all possible combinations of plans
	minPlans := q + 1
	var bestSolution []int
	
	// Try all possible combinations using bitmask
	for mask := 0; mask < (1 << q); mask++ {
		// Create a combined plan
		combined := make([][]int, n)
		for i := 0; i < n; i++ {
			combined[i] = make([]int, m)
		}
		
		// Apply selected plans
		selectedPlans := make([]int, 0)
		for i := 0; i < q; i++ {
			if (mask & (1 << i)) != 0 {
				selectedPlans = append(selectedPlans, i+1)
				for row := 0; row < n; row++ {
					for col := 0; col < m; col++ {
						if plans[i][row][col] == 1 {
							combined[row][col] = 1
						}
					}
				}
			}
		}
		
		// Check if this combination satisfies the requirements
		valid := true
		for i := 0; i < n; i++ {
			for j := 0; j < m; j++ {
				if initialState[i][j] == 1 && combined[i][j] == 1 {
					valid = false
					break
				}
				if initialState[i][j] == 0 && combined[i][j] == 0 {
					valid = false
					break
				}
			}
			if !valid {
				break
			}
		}
		
		if valid && len(selectedPlans) < minPlans {
			minPlans = len(selectedPlans)
			bestSolution = selectedPlans
		}
	}
	
	if minPlans == q+1 {
		fmt.Println(-1)
		return
	}
	
	fmt.Println(minPlans)
	for _, plan := range bestSolution {
		fmt.Printf("%d ", plan)
	}
	fmt.Println()
} 

import sys

# 处理过程用到的数据结构是二维的 bool 块
# 为了理解和思考方便，假设草地为 1 * m (011...)
# 然后这 1 行 bool 可以看成二进制表达的数字
# 那么草地杂物用数字 x 来表示，燃放计划用数字 y 来表示
#
# 想要杂物位置上不能放烟花，而所有空位都放烟花: 
#   就是 x 的所有为 1 的位上，y 必须为 0; 
#   而 x 的所有为 0 的位上，y 必须为 1
#   也就是 x | y == 0b(1111...) 且 x & y == 0
#   那么 y = x ^ 0b(1111...)
# 多个燃放计划一起执行: 
#   那么总计划的值为 yn = y1 | y2 | y3 ...
# 
# 所以这个题目可以简化为：
# 在 y1, y2, y3, ..., yn 中, 找到最少数量的 y (a, b, c...), 使得
#   (ya | yb | yc | ...) == x ^ 0b(1111...) 


# 在 planInfos 中找到能满足 target 的合并的方案
# planInfos: 所有固定的方案
# idx: planInfos 的下标，这个下标前面的方案已经考虑过，后面的方案等待考虑
# clutterInfo: 杂物信息
# target: 所有合并的方案要满足的目标
# mergedInfo: 已经合并好的方案
# planStr: 已选入的所有方案的下标的字符串
#
# return (bool, str): 只要一找到合适的方案，马上就返回
def findPlans(planInfos, idx, clutterInfo, target, mergedInfo, planStr):
    if idx == len(planInfos):
        return (False, '')
    plan = planInfos[idx]
    if plan & clutterInfo != 0: # 这个方案与杂物冲突，直接跳到下一个方案去计算
        return findPlans(planInfos, idx+1, clutterInfo, target, mergedInfo, planStr)

    if plan | mergedInfo == target: # 找到了方案
        return (True, planStr + ' ' + str(idx + 1))

    # 既然要找最少的方案数量，倾向于先不选择当前方案
    b1 = findPlans(planInfos, idx+1, clutterInfo, target, mergedInfo, planStr)
    if b1[0]: return b1

    # 再考虑加上当前的方案
    return findPlans(planInfos, idx+1, clutterInfo, target, mergedInfo | plan, planStr + ' ' + str(idx + 1))

# 提取草地特征，或者提取燃放计划的特征
# 题目说 n, m <= 7, 那么 n * m < 64, 草地信息用 64 位存储就够了，用 int 肯定可以
def extractFeatures(lines: list[str]) -> int:
    feature = 0
    for line in lines:
        for ch in line:
            bit = 1 if ch == '1' else 0
            feature = (feature << 1) + bit
    return feature

n, m, q = map(int, input().split(' '))

clutterInfo = 0
planInfos = [0] * q

for i in range(q + 1):
    lines = []
    for _ in range(n):
        lines.append(input().strip())
    if i == 0:
        # 第一个块是杂物的信息
        clutterInfo = extractFeatures(lines)
    else:
        # 后面的块是烟花信息
        planInfos[i-1] = extractFeatures(lines)

# 全为 1 的草地
allFull = (1 << (n*m)) - 1
target = clutterInfo ^ allFull

res = findPlans(planInfos, 0, clutterInfo, target, 0, '')
if res[0]:
    count = res[1].count(' ')
    print(count)
    print(res[1].strip())
else:
    print(0)

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m=in.nextInt(),n=in.nextInt(),q=in.nextInt();in.nextLine();
        int [][]grass=new int[m][n];
        for(int i=0;i<m;++i){
            String g1=in.nextLine();
            
            for(int j=0;j<n;++j){
                grass[i][j]=Integer.parseInt(""+g1.charAt(j));
            }
        }
        int [][]an=new int[m][n];
        // int [][]temp=new int[m][n];
        ArrayList<combine> alist=new ArrayList<>();
        for(int k=0;k<q;++k){
            for(int i=0;i<m;++i){
                String g1=in.nextLine();
            for(int j=0;j<n;++j){
                an[i][j]=Integer.parseInt(""+g1.charAt(j));
            }
        }
        alist.add(new combine(m,n,an));
        }
        ArrayList<Integer> listbags=new ArrayList<>();
        for(int i=0;i<q;++i){
            listbags.add(i+1);
        }
        bags(new combine(m,n,grass),new ArrayList<combine>(),alist,new boolean[q],listbags,new combine(m,n,grass));
        int allzero[][]=new int[m][n];
        combine zero=new combine(m,n,allzero);
        for(int i=0;i<q;++i){
            if(isconOk(alist.get(i),new combine(m,n,grass))){
                zero=zero.Numberadd(alist.get(i));
            }
        }
        if(!isFull(m,n,zero.Numberadd(new combine(m,n,grass)))){
            System.out.println(-1);
        }
        else{System.out.println(listbags.size());
        for(int i=0;i<listbags.size();++i){
            System.out.print(listbags.get(i)+" ");
        }}

    }
    private static void bags(combine now,ArrayList<combine> bagsnow,ArrayList<combine> total,boolean used[],ArrayList<Integer>usedbag,combine beginner){
        if(isFull(now.a.length,now.a[0].length,now)&&usedbag.size()>lenused(used)){
            ArrayList<Integer>temp=new ArrayList<>();
            temp=boltoArr(used);
            usedbag.clear();
            usedbag.addAll(temp);return;
        }

        for(int i=0;i<total.size();++i){
            if(!used[i]&&isconOk(total.get(i),beginner)){
                used[i]=true;
                bagsnow.add(total.get(i));
                bags(now.Numberadd(total.get(i)),bagsnow,total,used,usedbag,beginner);
                bagsnow.remove(bagsnow.size()-1);
                used[i]=false;
            }
        }

    }

    private static boolean isconOk(combine a,combine b){
        combine c=a.Numberadd(b);
        for(int i=0;i<c.a.length;++i){
            for(int j=0;j<c.a[0].length;++j){
                if(c.a[i][j]>=2)return false;
            }
        }
        return true;
    }
    private static int lenused(boolean[]used){
        int count=0;
        for(int i=0;i<used.length;++i){
            if(used[i]){
                count++;
            }
        }
        return count;
    }
    private static ArrayList<Integer> boltoArr(boolean[] used){
        ArrayList<Integer> alist=new ArrayList<>();
        for(int i=0;i<used.length;++i){
            if(used[i]){
                alist.add(i+1);
            }
        }
        return alist;
    }
    private static boolean isFull(int m,int n,combine a){
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(a.a[i][j]==0){
                    return false;
                }
            }
        }
        return true;
    }
    
}
class combine{

    int a[][];
    combine(int m,int n,int a[][]){
        int an[][]=new int[m][n];
        for(int i=0;i<m;++i){
            System.arraycopy(a[i],0,an[i],0,n);
            // for(int j=0;j<n;++j){
            //     this.a[i][j]=a[i][j];
            // }
        }
        this.a=an;
    }
    public combine Numberadd(combine b){
        int m=this.a.length,n=this.a[0].length;
        int c[][]=new int[m][n];
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                c[i][j]=this.a[i][j]+b.a[i][j];
            }
        }
        combine retc=new combine(m,n,c);
        return retc;
    }
}