P2622 关灯问题

小小注解：

1.

vis：表示到达该状态的步数（min）+1， 

因为我们是从开始状态 穷举，所以每次到一个新状态（之前没有到过的状态）就是最小步数。

如何判断是否是一个新状态呢，vis 知道，如果是新状态 vis=0；

另外，把开始状态设置为1，设置为 0 的话，程序就会把开始状态当作一个新状态，而开始状态当然不是一个新状态。

11.

开： 初始：1 0 1 0                                 关： 初始：1 0 1 0

           开： 1 1 0 0     （|）                               关： 1 1 0 0

        结果： 1 1 1 0                                        结果： 0 0 1 0

         初始 | 开 = 结果                                      ~关： 0 0 1 1     （&）

                                                                       初始 &(~ 关） = 结果 

111.

开始状态的得到：

例: n=4时；开始状态：1 1 1 1，即 (1<<n)-1 ;

注意：括号不能省，以为 1<<n-1 = 1<<(n-1);

#include<iostream>
#include<queue>
using namespace std;
int a[3300],b[3300]; //开灯 关灯 一个操作拆成两个 分别存在 a b中
int vis[3300];    //到达该状态的步数+1； 
//对于一种状态 1改灯开 0关
int main(){int n,m; cin>>n>>m;for(int i=0;i<m;i++)for(int j=0;j<n;j++){int x; scanf("%d",&x);a[i]<<=1; b[i]<<=1;if(x==1)  b[i]++;if(x==-1) a[i]++; }queue<int>q;q.push((1<<n)-1);vis[(1<<n)-1]=1;while(q.size()){int num=q.front(); q.pop();for(int i=0;i<m;i++){int temp=num|a[i];temp=temp&(~b[i]);if(vis[temp]) continue;vis[temp]=vis[num]+1; q.push(temp);if(temp==0){printf("%d",vis[0]-1); return 0;}}}printf("-1");return 0;
}