P2622 关灯问题II【状态压缩+BFS】

传送门
这题需要对状压及位运算有一定的了解：首先要判断某一位的灯是开的还是关的，才能进行修改。
具体解法：对队首的某一状态，枚举每一个开关灯操作，记录到达这一新状态的步数（也就是老状态 + 1），若是最终答案，输出，若不是，压入队列。
也就是说：我们把初始状态，用每个操作都试一遍，就产生了许多新的状态，再用所有操作一一操作新状态，就又产生了新的新状态，我们逐一尝试，直到有目标状态为止，这可以通过BFS实现。常规操作。

#include<bits/stdc++.h>
using namespace std;
const int N=2048;
int m,num; 
int a[N][N];
int d[N];
void bfs(int n){
	queue<int> q;
	q.push(n);d[n]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		if(u==0) return;
		for(int i=1;i<=m;i++){
			int now=u;
			for(int j=1;j<=num;j++){
				if(a[i][j]==1) {if(now&(1<<(j-1))) now^=(1<<(j-1));}
				if(a[i][j]==-1)  now|=(1<<(j-1)); 
			}
			if(d[now]==-1){
				d[now]=d[u]+1;
				q.push(now);
			} 
		}
	}
}
int main(){
	cin>>num>>m;
    int n = (1 << (num)) - 1;
    for(int i = 1;i <= m;i++){
        for(int j = 1;j <= num;j++){
            cin>>a[i][j];
            }
    }
    memset(d,-1,sizeof(d));
	bfs(n);
	cout<<d[0];
    return 0;
}