题解 | 小心火烛的歪

用回溯法做，fireworks函数是回溯函数，如果填满了，且步数更少，就记录结果。重载了加减法方便一点。

origin数组是记录的杂物，用于checkstone函数确保烟花没有放在杂物上面。

#include <iostream>
#include<vector>
using namespace std;
int minresult;
vector<int>final;
vector<vector<char>> operator+(const vector<vector<char>>a,
const vector<vector<char>>b) {
    int n = a.size(), m = a[0].size();
    vector<vector<char>>result(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            result[i][j] = a[i][j] + b[i][j] - '0';
        }
    }
    return result;
}
vector<vector<char>> operator-(const vector<vector<char>>a,
const vector<vector<char>>b) {
    int n = a.size(), m = a[0].size();
    vector<vector<char>>result(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            result[i][j] = a[i][j] - b[i][j] + '0';
        }
    }
    return result;
}
bool checkfull(vector<vector<char>>a) {
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < a[0].size(); j++) {
            if (a[i][j] == '0') {
                return false;
            }
        }
    }
    return true;
}
bool checkstone(vector<vector<char>>& origin,vector<vector<char>>& a){
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < a[0].size(); j++) {
            if(origin[i][j]=='1'&&a[i][j]=='1'){
                return false;
            }
        }
    }
    return true;
}
void fireworks(int q, int result, vector<vector<vector<char>>>& plans,
               int index,
               vector<vector<char>> states, vector<int>& plancode,vector<vector<char>>& origin) {
    if (checkfull(states)) {
        if (result < minresult) {
            minresult = result;
            final = plancode;
        }
        return;
    }
    for (int i = index; i < q; i++) {
        if (checkstone(origin,plans[i])) {
            states = states + plans[i];
            plancode.push_back(i + 1);

            fireworks(q, result + 1, plans, index + 1, states, plancode,origin);
            states = states - plans[i];
            plancode.pop_back();
        }

    }
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<char>> states(n, vector<char>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> states[i][j];
        }
    }
    vector<vector<vector<char>>>plans(q, vector<vector<char>>(n, vector<char>(m)));
    for (int i = 0; i < q; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                cin >> plans[i][j][k];
            }
        }
    }
    vector<int>plancode;
    minresult = q + 1;
    fireworks(q, 0, plans, 0, states, plancode,states);
    if (minresult < q + 1) {
        cout << minresult << endl;
        for (int i : final) {
            cout << i << ' ';
        }
    } else {
        cout << -1;
    }

}