题目描述
现有 $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$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#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复杂了。