题解 | 小心火烛的歪

// 嘿嘿嘿！！！ 看段姐姐给你们讲
// 1. 输入 n,m,q
// 2. 输入草地状态 
// 3. 目标矩阵的输入
// 4. 创容器，输入计划
// 5. 遍历所有可能的计划组合 计算当前计划组合里面的计划数
// 6. 选计划数少的，如果当前计划数 >最小计划数，当前这个就跳过
// 7. 把计划组合选出来了，按照计划组合，对应的位置放‘1’ 存入 模仿矩阵中
// 8. 检查模仿矩阵是否等于目标矩阵，如果不等于，就淘汰这个组合
// 9. 如果模仿矩阵等于目标矩阵，且他的计划数少 让最少计划数为他，最优计划组合为他
// 10.输出无解的情况
// 11. 输出最少计划数量
// 12. 输出每一个计划的计划编号 每个计划编号 与编号之间输出空格。用个标记
#include <bits/stdc++.h>
using namespace std;
  
int main() {
    int n, m, q;
    cin >> n >> m >> q;
      
    // 1. 读取草地状态
    vector<string> grass(n);
    for(int i = 0; i < n; i++) {
        cin >> grass[i];
    }
      
    // 2. 计算目标矩阵：杂物处为0，无杂物处为1
    vector<string> target(n, string(m, '0'));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grass[i][j] == '0') {
                target[i][j] = '1';  // 空地需要放烟花
            }
            // 杂物处保持0（不放烟花）
        }
    }
      
    // 3. 读取所有计划
    vector<vector<string>> plans(q, vector<string>(n));
    for(int k = 0; k < q; k++) {
        for(int i = 0; i < n; i++) {
            cin >> plans[k][i];
        }
    }
      
    // 4. 暴力枚举所有计划组合
    int minCount = q + 1;  // 初始化为不可能的值
    int bestMask = -1;     // 保存最佳选择的掩码
      
    // 枚举所有掩码（0 到 2^q-1）
    for(int mask = 0; mask < (1 << q); mask++) {
        int planCount = __builtin_popcount(mask);  // 当前选择的计划数
          
        // 剪枝：如果已经不比当前最优解好，跳过
        if(planCount >= minCount) continue;
          
        // 计算当前组合的OR结果
        vector<string> result(n, string(m, '0'));
          
        for(int k = 0; k < q; k++) {
            if(mask & (1 << k)) {  // 第k个计划被选中
                for(int i = 0; i < n; i++) {
                    for(int j = 0; j < m; j++) {
                        if(plans[k][i][j] == '1') {
                            result[i][j] = '1';
                        }
                    }
                }
            }
        }
          
        // 检查是否等于目标
        bool match = true;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(result[i][j] != target[i][j]) {
                    match = false;
                    break;
                }
            }
            if(!match) break;
        }
          
        // 如果匹配且计划数更少，更新最优解
        if(match && planCount < minCount) {
            minCount = planCount;
            bestMask = mask;
        }
    }
      
    // 5. 输出结果
    if(minCount == q + 1) {
        // 无解
        cout << -1 << endl;
    } else {
        // 输出计划数量
        cout << minCount << endl;
          
        // 输出计划编号（从1开始）
        if(minCount > 0) {
            bool first = true;
            for(int k = 0; k < q; k++) {
                if(bestMask & (1 << k)) {
                    if(!first) cout << " ";
                    cout << k + 1;  // 编号从1开始
                    first = false;
                }
            }
            cout << endl;
        }
    }
      
    return 0;
}