题解 | 小心火烛的歪 [好虾头的题目]

#include <iostream>
#include <bits/stdc++.h>
#include <set>
#include <vector>
using namespace std;

void dfs(vector<int> bitmap, vector<vector<int>>& pick_bitmaps, int pos) {
    int len = bitmap.size();
    if (pos == len) {
        pick_bitmaps.emplace_back(bitmap);
        return ;
    }
    for (int i = 0; i < 2; ++i) {
        bitmap[pos] = i;
        dfs(bitmap, pick_bitmaps, pos + 1);
    }
    return;
}

void sumMatrix(vector<vector<int>>& m_main, vector<vector<int>>& m_sub) {
    for (int i = 0; i < m_main.size(); ++i) {
        for (int j = 0; j < m_main[0].size(); ++j) {
            m_main[i][j] += m_sub[i][j];
        }
    }
    return;
}

bool isGoodPlan(vector<vector<int>>& grass_map,
                vector<vector<vector<int>>>& plan_maps, vector<int>& bitmap) {
    vector<vector<int>> multi_plan_map(grass_map.size(),
                                       vector<int>(grass_map[0].size()));
    for (int i = 0; i < bitmap.size(); ++i) {
        if (bitmap[i] == 1) {
            sumMatrix(multi_plan_map, plan_maps[i]);
        }
    }
    for (int i = 0; i < grass_map.size(); ++i) {
        for (int j = 0; j < grass_map[0].size(); ++j) {
            if (grass_map[i][j] == 1 && multi_plan_map[i][j] > 0 || grass_map[i][j] == 0 &&
                    multi_plan_map[i][j] == 0)
                return false;
        }
    }

    return true;
}

int main() {
    int n, m, q;
    char c;
    cin >> n >> m >> q;
    vector<vector<int>> grass_map(n, vector<int> (m));
    vector<vector<vector<int>>> plan_maps;
    vector<vector<int>> pick_bitmaps;
    vector<int> bitmap(q, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> c;
            grass_map[i][j] = c - '0';
        }
    }
    for (int i = 0; i < q; ++i) {
        vector<vector<int>> plan_map(n, vector<int> (m));
        for (int j = 0; j < n; ++j) {
            for (int k = 0 ; k < m; ++k) {
                cin >> c;
                plan_map[j][k] = c - '0';
            }
        }
        plan_maps.emplace_back(plan_map);
    }

    dfs(bitmap, pick_bitmaps, 0);

    int bitmap_index = -1;
    int less_plan = q + 1;
    for (int i = 0; i < pick_bitmaps.size(); ++i) {
        if (isGoodPlan(grass_map, plan_maps, pick_bitmaps[i])) {
            int pcnt = 0;
            for(auto n:pick_bitmaps[i]){
                if(n == 1)
                    ++pcnt;
            }
            if (pcnt < less_plan) {
                less_plan = pcnt;
                bitmap_index = i;
            }
        }
    }

    if (bitmap_index >= 0) {
        int plan_cnt = 0;
        for (int i = 0; i < q; ++i) {
            if (pick_bitmaps[bitmap_index][i] == 1) {
                ++plan_cnt;
            }
        }
        cout << plan_cnt << endl;
        for (int i = 0; i < q; ++i) {
            if (pick_bitmaps[bitmap_index][i] == 1) {
                cout << i + 1 << " ";
            }
        }
    } else {
        cout << -1;
    }
    return 0;
}