UVa 10318 - Security Panel

链接

传送门

题意

开关灯类问题,给出$n*m(1 \leq n,m \leq 5)$的矩阵,开始全灭,再给出开灯的影响矩阵,输出让所有灯全亮开灯次数最少的方案,无解输出“Impossible.”。

思路

可以枚举第一排之后验证,但感觉不太好写。于是直接用中途相遇搞了,枚举一半的灯最后的状态,再枚举另一半,如果两者异或为全集,就可以完成,选择开灯次数最小的输出。时间复杂度$O(2^{n/2}logn)$,略差于枚举第一排的算法,但对于这个数据量来说,足够了。

代码

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 6;
int n, m;
int msk[maxn * maxn];
map<int, int> dict;
inline void Mask(int r, int c, int& x) {
if (r < 0 || c < 0 || r >= n || c >= m) {
return;
}
x |= 1 << (r * m + c);
}
inline int bitcnt(int x) {
int res = 0;
while (x) {
x &= (x - 1);
++res;
}
return res;
}
int main() {
int t = 0;
while (~scanf("%d%d", &n, &m) && (n || m)) {
memset(msk, 0, sizeof msk);
for (int i = 0; i < 3; ++i) {
char s[5];
scanf("%s", s);
for (int j = 0; j < 3; ++j) {
if (s[j] == '*') {
for (int r = 0; r < n; ++r) {
for (int c = 0; c < m; ++c) {
Mask(r + i - 1, c + j - 1, msk[r * m + c]);
}
}
}
}
}
printf("Case #%d\n", ++t);
dict.clear();
int num = n * m, n1 = num >> 1, n2 = num - n1, s1 = 1 << n1, s2 = 1 << n2, S = (1 << num) - 1;
for (int i = 0; i < s1; ++i) {
int tmp = 0, cnt = 0;
for (int j = 0; j < n1; ++j) {
if (i & (1 << j)) {
tmp ^= msk[j];
++cnt;
}
}
if (!dict.count(tmp) || bitcnt(dict[tmp]) > cnt) {
dict[tmp] = i;
}
}
bool ok = false;
int ans = -1;
for (int i = 0; i < s2; ++i) {
int tmp = 0, cnt = 0;
for (int j = 0; j < n2; ++j) {
if (i & (1 << j)) {
tmp ^= msk[n1 + j];
++cnt;
}
}
tmp ^= S;
if (dict.count(tmp) && bitcnt(dict[tmp]) + cnt < bitcnt(ans)) {
ok = true;
ans = dict[tmp] + (i << n1);
}
}
if (!ok) {
puts("Impossible.");
}
else {
bool flag = true;
for (int i = 0; i < num; ++i) {
if (ans & (1 << i)) {
if (flag) {
flag = false;
}
else {
putchar(' ');
}
printf("%d", i + 1);
}
}
puts("");
}
}
return 0;
}

支付宝扫码领红包