lp2622 关灯问题II

显然，对于某个状态，按下某个按钮之后，一定会得到另一个状态。
而灯的状态最大只有\(2^10\)。
故而考虑建一张图，2^n个点，m条边，那么答案就是从0到2^n-1的最短距离。
直接BFS即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int INF=0x3f3f3f3f;
int n,m;
queue<int> q;
int dep[1025],vis[1025];
int a[15],b[105],c[105];
inline int bfs(){
	for(int i=0;i<(1<<n);++i){
		dep[i]=INF;
	}
	q.push(0);
	dep[0]=0;
	int p,v;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=1;i<=m;++i){
			v=(p|b[i])&c[i];
			if(dep[v]>dep[p]+1){
				dep[v]=dep[p]+1;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return (dep[(1<<n)-1]^INF)?dep[(1<<n)-1]:-1;
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		b[i]=c[i]=0;
	}
	for(int i=1;i<=m;++i){
		for(int j=0;j<n;++j){
			scanf("%d",&a[j]);
			if(a[j]==1){
				b[i]|=(1<<j);
				c[i]|=(1<<j);
			}
			if(a[j]==0){
				c[i]|=(1<<j);
			}
		}
	}
	printf("%d\n",bfs());
}
int main(){
	init();
	return 0;
}