D-小心火烛的歪

思路： DFS求序列的组合问题，就是一个序列 1 ~ q，从序列里选一个数有哪些选法，选两个数有哪些选法，选三个数有哪些选法...（不考虑顺序）

选好了数之后就检查是否满足条件，怎么检查呢？

用一个二维数组存储选了的这些方案的最终结果，然后与原图进行比较，如果对于每一位异或结果都为 1，说明放杂物的地方不会放烟花，没有放杂物的地方一定会放烟花；如果异或结果是 0，那就不满足题意，直接退出，去找下一种方案

相似题目：医生

具体思路请看代码：

//		https://ac.nowcoder.com/acm/contest/96115/D


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

int n,m,q;
int vis[10];
int d[10];//记录选了哪些方案
bool sign;//是否满足条件，这个标记变量贯穿始终
vector<string> a(10);
void check(vector<vector<string>>& v, int k)
{
	vector<vector<int>> temp(n,vector<int>(m,0));//存所有方案得出的结果
	for(int i=0;i<k;i++)//选的方案
		for(int j=0;j<n;j++)//第i种方案的行
			for(int p=0;p<m;p++)//列
				temp[j][p] |= v[d[i]][j][p]-'0';//或运算，计算所有方案得出的结果
	sign=1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(((a[i][j]-'0') ^ temp[i][j]) != 1)//异或结果不为1，说明有杂物的地方会放烟花 或者 没有放杂物的地方却没有放烟花
			{
				sign=0;
				break;
			}
		}
	}
}

void dfs(vector<vector<string>>& v, int index, int x, int k)//index为当前下标，x为选了多少个方案，k为要选多少个方案
{
	if(x==k)
	{
		check(v,k);//检查是否满足条件
		if(sign)
		{
			cout<<k<<endl;
			for(int i=0;i<k;i++)
				cout<<d[i]+1<<" ";
			cout<<endl;
			return ;
		}
		return ;
	}
	for(int i=index+1;i<q;i++)
	{
		if(vis[i]==0)
		{
			vis[i]=1;
			d[x]=i;
			dfs(v,i,x+1,k);
			if(sign)return ;
			vis[i]=0;
		}
	}
}
void solve(){
	cin>>n>>m>>q;
	for(int i=0;i<n;i++)cin>>a[i];
	vector<vector<string>> v(q,vector<string>(n));//类似三维字符数组
	for(int i=0;i<q;i++)
		for(int j=0;j<n;j++)
			cin>>v[i][j];
	//特判全1的情况，这种情况输出0而不是-1
	sign=1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(a[i][j]=='0')
			{
				sign=0;
				break;
			}
		}
		if(!sign)break;
	}
	if(sign)
	{
		cout<<0;
		return ;
	}
	for(int i=1;i<=q;i++)//选一种方案，选两种方案...... q 种方案全选，遍历
	{
		for(int j=0;j<q;j++)vis[j]=0;//初始化
		dfs(v,-1,0,i);
		if(sign)return;
	}
	cout<<-1<<endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	t=1;
	//cin>>t;
	while(t--)
		solve();
}