题解 | 小心火烛的歪

该问题要求从给定的烟花燃放计划中选择一个子集，使得最终燃放结果满足：所有有杂物的位置（初始状态为1）不燃放烟花，所有无杂物的位置（初始状态为0）燃放烟花。最终目标是找到满足条件的最小子集（计划数量最少）。由于n、m、q的约束均小于等于7，可以采用暴力枚举的方法，遍历所有可能的计划子集，检查每个子集是否满足条件，并记录最小有效子集。

计算复杂度

• 子集数量：共有2^q个子集，q≤7，因此最多128个子集。
• 每个子集的处理：对于每个子集，需要更新最终状态矩阵（O(n×m×q)）和检查条件（O(n×m)）。由于n、m、q均≤7，最坏情况下每个子集处理操作数约为7×7×7=343次。
• 总复杂度：O(2^q × n × m × q)，在约束下最大约为128×343=43904次操作，效率可接受。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    // 存储草地状态 G
    vector<string> G(n);
    // 存储所有计划 P[q][n][m]
    vector<vector<string>> P(q, vector<string>(n));

    for (int i = 0; i < n; i++)
        cin >> G[i];
    for (int i = 0; i < q; i++)
        for (int j = 0; j < n; j++)
            cin >> P[i][j];

    int minP = q + 1;
    int bestK = -1;

    for (int k = 0; k < (1 << q); k++) {
        int curP = __builtin_popcount(k);
        if (curP >= minP)
            continue;
        // 计算最终燃放矩阵 R
        vector<string> R(n, string(m, '0'));
        for (int i = 0; i < q; i++) {
            if ((k >> i) & 1) {
                for (int r = 0; r < n; r++)
                    for (int c = 0; c < m; c++) {
                        if (P[i][r][c] == '1')
                            R[r][c] = '1';
                    }
            }
        }

        bool isValid = true;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (G[r][c] == '1' && R[r][c] == '1') {
                    isValid = false;
                    break;
                }
                if (G[r][c] == '0' && R[r][c] == '0') {
                    isValid = false;
                    break;
                }
            }
            if (!isValid)
                break;
        }

        if (isValid && curP < minP) {
            minP = curP;
            bestK = k;
        }
    }

    if (bestK == -1) {
        cout << "-1" << endl;
    } else {
        cout << minP << endl;
        bool first = true;
        for (int i = 0; i < q; i++) {
            if ((bestK >> i) & 1) {
                if (!first)
                    cout << " ";
                cout << (i + 1);
                first = false;
            }
        }
    }
}