题目描述：
有 n 盏灯和 m 个开关，每个开关可以操作若干盏灯。
操作有可能是关掉某个灯（1），如果那个灯开着，否则不管；
也可能是打开某个灯（-1），如果那个灯关着，否则不管。
现在灯全是开着的，请你求出最少多少次操作可以关掉所有灯。
输入格式：
第一行包含两个整数 n 和 m。
接下来 m 行，包含 n 个正整数 -1/0/1。1 表示关掉，-1 表示打开，0 表示不操作该盏灯。
输出格式：
输出一行一个整数，表示答案。
样例输入：
3
2
1 0 1
-1 1 0
样例输出：
2
数据规模：
对于100%数据 n<=10,m<=100
思路
-
用状态压缩将每盏灯的开关压为一个数字（1表示开，0表示关）。
-
用 f_i 表示从初始状态（即 2^n-1 ）状态到达状态i时的最少步数，因为是BFS，所以一开始搜到的即是最少的步数，一搜到0时便输出当前步数并退出，如果搜完了所有能搜到的状态也搜不到0便输出-1。
-
对于每个状态，将每个开关都试一遍，如果得到了新的状态就推入队列。
-
对于每个开关，如果 a_{i,j} 是1，就将该状态“与(&)”上 2^n-1-2^{j-1} ，如果是0就跳过，如果是-1，就将该状态“或(|)”上 2^{j-1} 。
剩下的就是bfs，没有什么注意事项
AC代码
#include<iostream>
#include<queue>
using namespace std;
int n,m,a[105][15];
queue<int> q;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
int dp[4096]; //最大2的(10+1)次方
for(int i=0;i<=(1<<n)-1;i++) dp[i]=999999999;
dp[(1<<n)-1]=0;
q.push((1<<n)-1);
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=1;i<=m;i++){
int x=now;
for(int j=1;j<=n;j++){
if(a[i][j]==0) continue;
if(a[i][j]==1) x &= (1<<n)-1-(1<<(j-1));
if(a[i][j]==-1) x |= 1<<(j-1);
}
if(x==0){
cout<<dp[now]+1<<endl;
return 0;
}else if(dp[now]+1<dp[x]){
dp[x]=dp[now]+1;
q.push(x);
}
}
}
cout<<-1<<endl;
}