AcWing 飞行员兄弟 二进制枚举
标签：i++ style font 还原 优化 cto else bool logs
这道题目和费解的开关https://www.cnblogs.com/fx1998/p/12767815.html类似一点点。
解题思路：
一共有16个开关，每个开关可以选择按一下或不按这两种状态。
所以可能的结果一共有2^16=65536，对于每种情况，再遍历一下4*4的矩阵看是否全是打开的，再乘以16，2^16 * 16 = 1,048,576?。再加上其他运算所用的时间，总时间复杂度很小，可以直接暴力。
但是费解的开关是5*5，所有可能的情况是2^25=33,554,432?，时间复杂度较高，所以不考虑暴力。
所以用一个16位的二进制数字，来表示进行的操作，0表示不按，1表示按。用二进制从0~2^16 - 1，枚举所有的情况。
将4*4棋盘的开关标号为：
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
这道题目还可以用二进制来优化，但没必要，暴力可过。
1 #include 2 using namespace std;
3 const int N = 5;
4 char g[N][N], bk[N][N];
5 typedef pairint, int> PII;
6 #define fi first
7 #define se second
8 int get(int x, int y) {
9 return x * 4 + y;
10 }
11 void turn_one(int x, int y) {
12 if (g[x][y] == ‘+‘) {
13 g[x][y] = ‘-‘;
14 } else {
15 g[x][y] = ‘+‘;
16 }
17 }
18 void turn_all(int x, int y) {
19 for (int i = 0; i 4; i++) {
20 turn_one(x, i);
21 turn_one(i, y);
22 }
23 turn_one(x, y);
24 }
25 int main() {
26 for (int i = 0; i 4; i++) {
27 cin >> g[i];
28 }
29 vector res;
30 for (int op = 0; op 1 16); op++) {
31 vector t;
32 memcpy(bk, g, sizeof g); //备份
33 for (int i = 0; i 4; i++) { //操作
34 for (int j = 0; j 4; j++) {
35 if (op >> get(i, j) & 1) {
36 t.push_back({i, j});
37 turn_all(i, j);
38 }
39 }
40 }
41 //判断灯泡是否全亮
42 bool flag = true;
43 for (int i = 0; i 4; i++) {
44 for (int j = 0; j 4; j++) {
45 if (g[i][j] == ‘+‘) {
46 flag = false;
47 }
48 }
49 }
50 if (flag) {
51 if (res.empty() || res.size() > t.size()) {
52 res = t;
53 }
54 }
55 memcpy(g, bk, sizeof g); //还原
56 }
57 cout endl;
58 for (int i = 0; i ) {
59 cout " " endl;
60 }
61 return 0;
62 }
AcWing 飞行员兄弟 二进制枚举
标签：i++ style font 还原 优化 cto else bool logs
原文地址：https://www.cnblogs.com/fx1998/p/12785188.html
评论