Luogu-P2622-关灯问题II

题目 P2622 关灯问题II

题目描述

现有 $n$ 盏灯，以及 $m$ 个按钮。每个按钮可以同时控制这 $n$ 盏灯——按下了第 $i$ 个按钮，对于所有的灯都有一个效果。按下 $i$ 按钮对于第 $j$ 盏灯，是下面 $3$ 中效果之一：如果 $a_{i,j}$ 为 $1$，那么当这盏灯开了的时候，把它关上，否则不管；如果为 $-1$ 的话，如果这盏灯是关的，那么把它打开，否则也不管；如果是 $0$，无论这灯是否开，都不管。

现在这些灯都是开的，给出所有开关对所有灯的控制效果，求问最少要按几下按钮才能全部关掉。

输入格式

前两行两个数，$n, m$。

接下来 $m$ 行，每行 $n$ 个数 $,a_{i, j}$ 表示第 $i$ 个开关对第 $j$ 个灯的效果。

输出格式

一个整数，表示最少按按钮次数。如果没有任何办法使其全部关闭，输出 $-1$。

思路：状态压缩bfs

因为 $n \leq 10$，所以可以用一个数字表示灯的开关状态。

基本定义

设 $state$ 表示当前灯的开关状态。

如果第 $i$ 个灯开启，那么 $state$（二进制）中的第 $i$ 位为 $1$（以最右边为第 $0$ 位）。

使用 $vis[state]$ 记录 $state$ 状态是否访问过。

按钮效果处理

• $1: x \rightarrow x \mathrm{and} 0$
• $0: x \rightarrow x$
• $-1: x \rightarrow x \mathrm{or} 1$

AC Code

// template v7
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

inline void minset(int &t, int other) {
    t = min(t, other);
}

inline void maxset(int &t, int other) {
    t = max(t, other);
}

const int inf = 0x7f7f7f7f;

const int N = (1 << 10) + 10;
const int M = 110;

int step[N];
bool vis[N];

int op[M][11];
int n, m;

int bfs() {
    int full = (1 << n) - 1;
    queue<int> q;
    q.push(full);
    vis[full] = true;
    while(q.size()) {
        int from = q.front();
        q.pop();
        for(int i = 1; i <= m; i++) {
            int state = from;
            for(int j = n - 1; j >= 0; j--) {
                int op_num = op[i][j];
                switch(op_num) {
                    case -1:
                        state |= (1 << j);
                        break;
                    case 1:
                        state &= (full ^ (1 << j));
                }
            }
            if(!vis[state]) {
                q.push(state);
                vis[state] = true;
                step[state] = step[from] + 1;
            }
            if(!state) {
                return step[state];
            }
        }
    }
    return -1;
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        for(int j = n - 1; j >= 0; j--) {
            cin >> op[i][j];
        }
    }
    cout << bfs() << endl;
    return 0;
}

补充

既然是状态压缩，为什么不用状压dp？

考虑时间复杂度：

• 有 $n$ 个灯泡，状态数为 $2^n$。
• 有 $m$ 种操作，因为灯泡的亮暗与操作顺序有关，所以需要枚举所有状态的全排列，约 $m!$ 种。
• 将它们相乘，时间复杂度为 $O(2^n \cdot m!)$。

所以，时间会炸，要用一些优化才行，但是这样反而比bfs复杂了。