这题的灯只有开或者关两种选择，数据范围又很小，很明显跟二进制有关系，所以肯定会想到位运算

了解位运算的可跳过分割线中的内容

若对位运算还不够了解，可以先参考一下大佬的博客

搬运：位运算总结(按位与,或,异或)

这里给几个小技巧：

1. 一个数异或上$0$等于他自己
2. 一个数或上一个$1$可以在该位置上添加一个$1$，即把$0$变为$1$，$1$不变
3. 一个数与上一个$1$可以判断该位置上是否为$1$

先来分析下题目

已知有$n$盏灯和$m$个按钮，每个按钮都可以影响某一些灯的开关状态，开始时所有灯都打开，求最少按几次按钮可以使灯全部关闭。

看到最少这个字眼的时候$Julao$们一定都浮想联翩想到了很多算法，但是如果是和位运算结合起来，也就是可以很简单地将一个状态转化为另一个一步就可以到达的状态时，自然地想到

BFS！！！

总体算法出来之后就来考虑位运算的部分有点长

我们把每个按钮对每盏灯的影响存在$ctrl$数组中，则$ctrl[i][j]$代表第$i$个按钮对第$j$盏灯产生的影响哪一种（$1$，$0$或者$-1$）。

每盏灯的开合明显用$1$、$0$来表示，而现在我们需要做的就是设计一种方法，把按钮的信息存到数组中，从而让我们在做下面操作时可以很快地得出按下某一个按钮后的新状态。

这是按下按钮对灯变化的规定

如果ctrl[i][j]为1，那么当这盏灯开了的时候，把它关上，否则不管；
如果为-1的话，如果这盏灯是关的，那么把它打开，否则也不管；
如果是0，无论这灯是否开，都不管。

那么怎么做呢？先让我们看看样例

3
2
1 0 1
-1 1 0

一开始灯的状态是$111$，当我们把它认为是一个二进制时，它可以变成十进制的$7$。由于按钮对灯的变化有$-1$、$1$、$0$三种数，所以我们需要分类（以下均用$1$、$0$表示灯的打开和关闭）：

1. 当某一个$ctrl[i][j]=1$时，按下按钮后灯$j$一定会变成$0$，而如果把这和位运算扯上关系，我们可以发现，当这盏灯开着，也就是二进制的从右边数的第$j$位是$1$，我们将其 异或 上一个二进制数，这个数除了从右边数的第$j$位为$1$之外全部为$0$，这样的话，若本处本为$1$，则会变为$0$，否则对原来的数无修改，符合上面“当这盏灯开了的时候，把它关上，否则不管”；
2. 当某一个$ctrl[i][j]=-1$时，按下按钮后灯$j$一定会变成$1$,这是只要 或 上一个和上方相同的二进制数，即除了从右边数的第$j$位为$1$之外全部为$0$，若本处本为$0$,则会变为$1$,否则不会修改；
3. 当某一个$ctrl[i][j]=0$时，直接跳过。

十分有点抽象哈，可以用笔模拟一下这个过程，弄明白之后就按照这个方法进行状态更新就好啦

上代码：

//Code By CXY
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1000010;//使得十进制最大的状态不会超过这个数字 

int n,m,light = 0;
int ctrl[101][11];
int que[MAXN][2];//que[i][0]表示该状态,que[i][1]表示走到该状态的步数 
bool vis[MAXN]={false};

int main() {
    cin >> n >> m;
    for(int i = 1;i <= m; ++i)
        for(int j = 1;j <= n; ++j)
            cin >> ctrl[i][j];//ctrl数组 
    int head=0,tail=1;//BFS标配~~ 
    que[head][0] = (1 << n) - 1;//这就是初始状态 -> 所有灯都开着，在十进制中间是 2^n - 1 
    que[head][1] = 0;
    vis[que[head][0]] = true;//已经到过此处 
    while(head < tail) {//BFS不解释 
        int step = que[head][1];//取出队头 
        int now = que[head][0];//如上 
        for(int i = 1;i <= m; ++i) {//枚举按下一个按钮 
            now = que[head][0];//每次都要重新赋值 
            for(int j = 1;j <= n; ++j) {//枚举被影响的每一盏灯 
                if(ctrl[i][j] == 1) {//情况 1 
                    if((now & (1 << (j - 1))))//如果该位置上的灯是亮着的 
                        now = (now ^ (1 << (j - 1)));//灭掉它 
                }
                if(ctrl[i][j] == -1) {//情况 2 
                    if(!(now & (1 << (j - 1))))//如果该位置上的灯是灭的 
                        now = now | (1 << (j - 1));//点亮它 
                }
            }
            if(now == 0) {//即最终状态 -> 全部熄灭 
                cout << step + 1 <<endl;//记得 +1 
                return 0;//直接退出 
            } 
            if(!vis[now]) {//如果没有到达过这种状态 
                que[tail][0] = now;//放到对位 
                que[tail++][1] = step + 1;//步数 +1，尾指针 +1 
                vis[now] = true;//标记 
            }
        }
        head++;//头指针 +1 
    }
    cout << -1 << endl;//若跳出while循环即为无解，输出 -1 
    return 0;//华丽丽地结束 
}

初二的$OIer$，请多关照