题解 | 小心火烛的歪

该题要求找到一个子集：使得所有的标注为0的草地都有烟花放且在杂物“1”上不能有烟花放，最终要找到一个使用计划数最少的子集。

因此，在输入计划时直接判断此计划中是否有烟花放在杂物上，若有则直接否定此计划。

随后进行dfs枚举，枚举每一种情况的可能，若达到要求，则ans存入最小的可能。

#include<bits/stdc++.h>
#define ll long long
#define all(a) a.begin(),a.end()
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define endl "\n"
#define vi(a) vector<int> a
#define vll(a) vector<long long> a
using namespace std;
const int NUM=10e5+7;
const ll MOD=1000000007;
ll n,k,ym,m;
char a[100][100],b[100][100],x[10][10][10];
vi(ans);
ll num,cnt,q;
bool f[10],c[100][100][100];
string s;
void dfs(int Q,vector<int> t){
    if (f[Q]) return ;
    // cout<<Q<<' '<<num<<'\n';
    if (num==cnt){
        if (t.size()<ans.size()||ans.empty()) ans=t;
        return ;
    }
    if (Q>q) return ;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) c[Q][i][j]=0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            // cout<<x[Q][i][j]<<' '<<b[i][j];
            if (x[Q][i][j]=='1'&&b[i][j]=='0'){
                b[i][j]='2';
                num++;
                c[Q][i][j]=1;
            }
        }
        // cout<<"\n";
    }
    if (Q!=0)t.push_back(Q);
    // cout<<num;
    for (int i=Q+1;i<=q+1;i++) dfs(i,t);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (c[Q][i][j]){
                b[i][j]='0';
                num--;
            }
        }
    }
    t.pop_back();
    return ;
}
void solve()
{
    cin>>n>>m>>q;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin>>a[i][j];
            if (a[i][j]=='0') cnt++;
        }
    }
    for (int Q=1;Q<=q;Q++){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                cin>>x[Q][i][j];
                if (x[Q][i][j]=='1'&&a[i][j]=='1'){
                    f[Q]=1;
                }
                // if (x==1&&a[i][j]==1) f=1;
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            b[i][j]=a[i][j];
        }
    }
    vi(tt);
    if (cnt==0){
        cout<<0;
        return ;
    }
    dfs(0,tt);
    if (ans.size()==0){
        cout<<-1;
        return ;
    }
    cout<<ans.size()<<"\n";
    for (int i=0;i<ans.size();i++) cout<<ans[i]<<' ';
	return ;
}
int main()
{
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	int T=1;
//	cin>>T;
	while(T--) solve();
	return 0;
}