洛谷 P2622 关灯问题II
程序员文章站
2024-03-23 22:54:28
...
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
输入样例
3
2
1 0 1
-1 1 0
输出样例
2
思路学习自 https://www.cnblogs.com/Tony-Double-Sky/p/9283254.html
做到这到题是因为做到一道状态压缩dp的题,看不太懂所以决定从较为简单的做起。状态压缩正如字面所讲,假如有很多串1和0来组成的字符串,每个1和0代表这一种含义,如果我们用数组去储存它,当我们想要将其中一串字符串进行移动转移的话,就要遍历每一个位置上的数将其转移,可想而知,这会相当的消耗时间。那么状态压缩就是将这一串1和0组成的数字看作是二进制数并转化成十进制储存,那么空间与时间都会得到相应的缩小,具体实现的原理请转至链接处。
\(口__口)/
下面是这道题的代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define met(a, b) memset(a, b, sizeof(a))
#define ll long long
using namespace std;
struct node {
int w, step;
};
int MAP[110][15];
int n, m;
int BFS(int s) {
queue<node> que;
que.push((node){s, 0});
int vis[2048] = {0};
vis[s] = 1;
while(!que.empty()) {
node t = que.front();
que.pop();
for(int i = 1; i <= m; i++) {
int now = t.w;
for(int j = 1; j <= n; j++) {
if(MAP[i][j] == 1) {
if(now & (1 << (j-1))) { //判断第j位是否为1
now = now ^ (1 << (j-1)); //将第j位修改为0
}
}
else if(MAP[i][j] == -1) {
now = now | (1 << (j-1)); //小技巧,无需判断直接取或,如果为1不变,为0变1
}
}
if(vis[now]) continue; //已经到达过的状态跳过
if(now == 0) return t.step+1; //如果状态达到要求就返回到这个状态的步数
vis[now] = 1;
que.push((node){now, t.step+1});
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
int s = (1 << n) - 1; //s为初始状态
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
cin >> MAP[i][j];
}
}
int re = BFS(s);
cout << re << endl;
return 0;
}