飞行员兄弟
飞行员兄弟
“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 $16$ 个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个 $4 \times 4$ 的矩阵，您可以改变任何一个位置 $\left\lbrack {i,j} \right\rbrack$ 上把手的状态。
但是，这也会使得第 $i$ 行和第 $j$ 列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行，每行包含四个把手的初始状态。
符号 $+$ 表示把手处于闭合状态，而符号 $-$ 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数 $N$，表示所需的最小切换把手次数。
接下来 $N$ 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围
$1 \leq i,j \leq 4$
输入样例：
-+-- ---- ---- -+--
输出样例：
6 1 1 1 3 1 4 4 1 4 3 4 4
解题思路
按照题意，当要改变某个坐标$\left( {x, y} \right)$的状态，第$x$行和第$y$列的状态都要改变。我们发现每个位置最多只能改变一次状态，因为改变两次的话就变成原来的状态，其实就是没有改变过。改变三次的话其实等价于改变一次的状态。所以为了得到最小的改变次数，我们规定每个位置的状态最多只能改变一次。也就是$\left( {x, y} \right)$这个位置最多只能改变一次状态。同时，改变状态位置的顺序是不影响结果的，也就是说对于一组确定的方案（确定改变哪些位置的状态），选择位置的先后改变顺序可以是任意的，得到的结果都是相同的。因为每个位置的状态只与改变这个位置状态的次数有关，所以先后顺序是无所谓的。
其实对于所有的开关问题都有两个性质（开关问题指当改变某个位置状态的时，某些位置的状态也会同时改变）：
- 每个开关最多只按一次。
- 按开关的顺序可以是任意的。
由于数据范围很小，所以可以直接用暴力枚举。
下面给出用位运算与状态压缩的做法，时间复杂度是$O\left( {2^{16} \times 16} \right)$。
我们把$4 \times 4$的格子压缩成一个$16$位的二进制数（$0 \sim 15$）。如果格子的坐标为$\left( {x, y} \right)$，那么就对应二进制数的第$4 \cdot x + y$位。反过来二进制数的第$i$位，对应格子的坐标为$\left( {i/4,~i\% 4} \right)$。
我们每个位置可以选择改变或不改变状态，一共有$4 \times 4 = 16$个位置，共$2^{16}$中选择，所以枚举的区间是$0 \sim 2^{16} - 1$，看一下这些数在二进制下中的每一位，如果某一位为$1$，说明要改变这一个位置的状态。
如果某一位是$1$，那么我们怎么快速实现改变某行某列状态的操作呢？这个也可以用位运算来实现。因为我们状态的改变为从$0$改变到$1$，从$1$改变到$0$，所以可以用异或来实现。因为每个格子都对应二进制状态的某一位，所以我们只需要找到要改变的某一行和某一列的所有位置，然后把这些位置对应的二进制位置都异或$1$，就可以实现状态$0, 1$的改变了。
因此我们可以进行预处理，找到每个位置要改变状态时，对应要异或的数是多少，存到数组里面。到时候枚举到某个要改变状态的位置时就可以直接查表得到，进行异或，时间复杂度就可以达到$O \left( 1 \right)$了。
所以当我们确定一个方案后，把这个方案实现一遍，复杂度是$O \left( 16 \right)$的。一共$2^{16}$种方案，所以时间复杂度就为$O\left( {2^{16} \times 16} \right)$。
最后枚举$2^{16}$次就可以了。
AC代码如下：
1 #include2 #include 3 #include 4 using namespace std; 5 6 typedef pair<int, int> PII; 7 8 const int N = 20; 9 10 int change[N]; 11 12 int main() { 13 int state = 0; 14 for (int i = 0; i < 4; i++) { 15 char str[N]; 16 scanf("%s", str); 17 18 for (int j = 0; j < 4; j++) { 19 if (str[j] == '+') state += 1 << i * 4 + j; // '+'对应1，'-'对应0 20 } 21 } 22 23 // 预处理出来每个位置改变时要异或的数 24 for (int i = 0; i < 4; i++) { 25 for (int j = 0; j < 4; j++) { 26 int idx = i * 4 + j; // 将格子的坐标转换为对应的二进制位置 27 for (int k = 0; k < 4; k++) { 28 change[idx] += (1 << i * 4 + k) + (1 << k * 4 + j); 29 } 30 change[idx] -= 1 << i * 4 + j; // 容斥原理，(i, j)这个位置被加了两次，所以最后要减一次 31 } 32 } 33 34 vector ret(N); 35 for (int i = 0; i < 1 << 16; i++) { 36 int t = state; 37 vector vec; 38 for (int j = 0; j < 16; j++) { 39 if (i >> j & 1) { 40 t ^= change[j]; // 二进制某位为1表示要改变这个格子的状态，直接查表异或 41 vec.push_back({j / 4, j % 4}); 42 } 43 } 44 45 // t == 0意味着整个二进制数为0，表示所有格子都是'-' 46 if (t == 0 && ret.size() > vec.size()) ret = vec; 47 } 48 49 printf("%d\n", ret.size()); 50 for (auto &it : ret) { 51 printf("%d %d\n", it.first + 1, it.second + 1); 52 } 53 54 return 0; 55 }
由于每个格子有两种选择，一个是改变状态，另外一个是不改变状态，所以还可以用dfs来做。
对应的AC代码如下：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 typedef pair<int, int> PII; 8 9 const int N = 10; 10 11 vector ans(20), ret; 12 char graph[N][N]; 13 14 void turn(int x, int y) { 15 for (int i = 0; i < 4; i++) { 16 graph[x][i] = graph[x][i] == '+' ? '-' : '+'; 17 graph[i][y] = graph[i][y] == '+' ? '-' : '+'; 18 } 19 graph[x][y] = graph[x][y] == '+' ? '-' : '+'; 20 } 21 22 void dfs(int x, int y) { 23 if (y == 4) { 24 x++, y = 0; 25 if (x == 4) { 26 for (int i = 0; i < 4; i++) { 27 if (strcmp(graph[i], "----")) return; 28 } 29 if (ans.size() > ret.size()) ans = ret; 30 31 return; 32 } 33 } 34 35 turn(x, y); 36 ret.push_back({x, y}); 37 dfs(x, y + 1); 38 39 turn(x, y); 40 ret.pop_back(); 41 dfs(x, y + 1); 42 } 43 44 int main() { 45 for (int i = 0; i < 4; i++) { 46 scanf("%s", graph + i); 47 } 48 49 dfs(0, 0); 50 51 printf("%d\n", ans.size()); 52 for (auto &it : ans) { 53 printf("%d %d\n", it.first + 1, it.second + 1); 54 } 55 56 return 0; 57 }
bfs也可以做。因为每个位置规定最多改变一次，所以如果发现某个情况之前出现过，这就意味着某个位置被改变了两次状态，那么这个情况就不可以被压入队列。
对应的AC代码如下：
1 #include2 #include <string> 3 #include 4 #include 5 #include 6 using namespace std; 7 8 typedef pair<int, int> PII; 9 10 string ed(16, '-'); 11 unordered_map<string, int> dist; // 记录变化到某个情况已改变的位置的数量 12 unordered_map<string, string> pre; // 记录某个情况是通过哪一个情况变化过来的 13 unordered_map<string, PII> mp; // 记录某个情况是通过哪一个位置变化过来的 14 15 int bfs(string &str) { 16 queue<string> q; 17 q.push(str); 18 dist[str] = 0; 19 mp[str] = {-1, -1}; 20 21 while (!q.empty()) { 22 string s = q.front(); 23 q.pop(); 24 25 // 如果发现全部格子都是'-'，退出 26 if (s == ed) break; 27 28 for (int i = 0; i < 4; i++) { 29 for (int j = 0; j < 4; j++) { 30 string t = s; 31 t[i * 4 + j] = t[i * 4 + j] == '+' ? '-' : '+'; 32 for (int k = i * 4; k < (i + 1) * 4; k++) { 33 t[k] = t[k] == '+' ? '-' : '+'; 34 } 35 for (int k = j; k < j + 24; k += 4) { 36 t[k] = t[k] == '+' ? '-' : '+'; 37 } 38 39 // 如果发现某个情况之前记录过，说明某个位置改变了两次状态，不能压入队列 40 if (dist.count(t)) continue; 41 dist[t] += dist[s] + 1; 42 pre[t] = s; 43 mp[t] = {i + 1, j + 1}; 44 q.push(t); 45 } 46 } 47 } 48 49 return dist[ed]; 50 } 51 52 void print_path(string &str) { 53 if (mp[str].first == -1) return; 54 55 print_path(pre[str]); 56 printf("%d %d\n", mp[str].first, mp[str].second); 57 } 58 59 int main() { 60 string str; 61 for (int i = 0; i < 4; i++) { 62 char s[5]; 63 scanf("%s\n", s); 64 str += s; 65 } 66 67 printf("%d\n", bfs(str)); 68 print_path(ed); 69 70 return 0; 71 }
参考资料
AcWing 116. 飞行员兄弟：https://www.acwing.com/video/93/