题解 | 小心火烛的歪

// 看段姐姐给你们写的，那叫一个通透
// 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;
    //2. 草坪
    vector<string> grass(n);
    for(int i = 0;i<n;i++){
        cin >> grass[i];
    }
    // 3. 目标矩阵
    vector<string> mubiao(n,string(m,'0'));
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
        if(grass[i][j]== '0'){
            mubiao[i][j]= '1';
        }
    }
    }
    //4. 创容器，输入计划
    vector<vector<string>> jihua(q,vector<string>(n));
    for(int i = 0;i<q;i++){
        for(int j = 0;j<n;j++){
            cin>>jihua[i][j];
        }
    }
    // 5. 遍历所有可能的计划组合 计算当前计划组合里面的计划数
    int min = q+1;
    int bestmask = -1;
    
    for(int mask = 0;mask<(1<<q);mask++){
        int jihuashu = __builtin_popcount(mask);
        if(jihuashu > min) continue;
    // 7. 把计划组合选出来了，按照计划组合，对应的位置放‘1’ 存入 模仿矩阵中
    vector<string> mofang(n,string(m,'0'));
    for(int i = 0;i<q;i++){
        if(mask&(1<<i)){
        for(int j = 0;j<n;j++){
            for(int z = 0;z<m;z++){
                if(jihua[i][j][z] == '1'){
                    mofang[j][z] = '1';
                }
            }
        }
        }
    }
    // 8. 检查模仿矩阵是否等于目标矩阵，如果不等于，就淘汰这个组合
    bool mm = true;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(mofang[i][j] != mubiao[i][j]){
                mm = false;
                break;
            }
        }
        if(!mm) break;
    }
    // 9. 如果模仿矩阵等于目标矩阵，且他的计划数少 让最少计划数为他，最优计划组合为他
    if(mm&& jihuashu < min){
        min = jihuashu;
        bestmask = mask;
    }
    }
    // 10.输出无解的情况
// 11. 输出最少计划数量
// 12. 输出每一个计划的计划编号 每个计划编号 与编号之间输出空格。用个标记
   if(min == q+1){
    cout << -1 <<endl;
   }
   else{
    cout << min << endl;
    bool a = true;
    if(min>0){
    for(int i = 0;i<q;i++){
        if(bestmask&(1<<i)){
            if(!a) cout << " ";
            cout << i+1;
            a = false;
        }
    }
    cout << endl;
   }
   }
   return 0;
}