题解 | 小心火烛的歪

import sys

def merge(fire,plan):#实施计划
    for i in range(len(fire)):
        fire[i] = fire[i] | plan[i]

def checkok(grass,plan):#检查计划是否可行
    for i in range(len(grass)):
        if grass[i] & plan[i]:
            return False
    else:
        return True

def isfull(grass,fire,m):#检查是否所有空草地都有烟花燃放
    for i in range(len(grass)):
        s = bin(grass[i] | fire[i])[2:]
        if s != '1'*m:
            return False
    return True
        
def way(grass,fire,plans,used,q,m,k):
    if isfull(grass,fire,m):
        if sum(used) > k:#如果使用计划数超过限制就不行
            return []
        else:
            return used#否则返回计划使用情况
    elif not plans:#如果草坪没满，但计划都不行就返回空列表
        return []
    plan = plans.pop(0)
    temp = way(grass,fire[:],plans[:],used[:],q,m,k)#如果不使用本计划的情况
    if temp:
        return temp
    if checkok(grass,plan):#如果本计划可行，则使用本计划
        used[q-len(plans)-1] = 1
        merge(fire,plan)
        temp = way(grass,fire[:],plans[:],used[:],q,m,k)
        if temp:
            return temp
      
while True:
    try:
        n,m,q = map(int,input().split())
        grass = []#草坪杂物分布
        plans = []#燃放计划
        for _ in range(n):
            grass.append(int(input(),2))
        for _ in range(q):
            temp = []
            for _ in range(n):
                temp.append(int(input(),2))
            plans.append(temp)
        fire = [0]*n#已经燃放烟花的位置
        used = [0]*q#计划实施情况
        for k in range(1,q+1):#限制燃放计划数，保证总计划数最小
            out = way(grass,fire[:],plans[:],used[:],q,m,k)
            if out:
                print(sum(out))
                lst = [i + 1 for i in range(q) if out[i]]
                print(' '.join(map(str,lst)))
                break
        else:
            print('-1')
            
    except:
        break