题目：P2622 关灯问题
题意：
有 m 盏灯，n 个开关。第 i 个按钮控制第 j 盏灯。
分三种情况：
- 输入 0 时，不管。
- 输入 1 时，灯必为关。
- 输入 -1 时，灯必为开。
求从全开到全关的最小步数。
思路：状态压缩DP
整体框架：
- 将 11111\ldots 放入一个变量中（利用二进制）。
- 使用搜索 - 广搜（BFS）。
- 起点是全是 1，状态表示成 01 数。
对于每一种情况，需要求 m 种情况：
- 若为 1：
now = now | (1 << (j-1))// 将第 j 位设置为 1 - 若为 -1：
now = now & (~(1 << (j-1)))// 将第 j 位设置为 0
灯只有开或关，数据范围小。
AC代码：
#include<bits/stdc++.h>
#define N 1001
using namespace std;
int n, m, a[N][N], step[N], vis[N];
bool flag = true;
queue<int> q;
void bfs(int x) {
q.push(x);
while(!q.empty()) {
int now = q.front(), num = q.front();
if (now == 0) {
cout << step[now]; // 输出当前步数，程序结束
flag = false; // 标记有解
return;
}
q.pop();
for(int i = 1; i <= m; i++) {
now = num;
for(int j = 1; j <= n; j++) {
if (a[i][j] == -1) { // 若为 -1，将第 j 位变为 1
now = now | (1 << (j-1));
} else if (a[i][j] == 1) { // 若为 1，将第 j 位变为 0
now = now & (~(1 << (j-1)));
}
}
if (!vis[now]) { // 如果未访问过，入队并标记，步数 +1
q.push(now);
step[now] = step[num] + 1;
vis[now] = 1;
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
bfs((1 << n) - 1); // 起点状态，广搜求解
if (flag == true) {
cout << -1; // 无解输出 -1
}
return 0;
}
时间复杂度: O(m \times n)
空间复杂度: O(2^n)
