UVa 10318 - Security Panel

发表于 分类于 ， ， Disqus：

链接

传送门

题意

开关灯类问题，给出\(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;
}
相关文章