飞行员兄弟

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 $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)$这个位置最多只能改变一次状态。同时，改变状态位置的顺序是不影响结果的，也就是说对于一组确定的方案（确定改变哪些位置的状态），选择位置的先后改变顺序可以是任意的，得到的结果都是相同的。因为每个位置的状态只与改变这个位置状态的次数有关，所以先后顺序是无所谓的。

　　其实对于所有的开关问题都有两个性质（开关问题指当改变某个位置状态的时，某些位置的状态也会同时改变）：

1. 每个开关最多只按一次。
2. 按开关的顺序可以是任意的。

　　由于数据范围很小，所以可以直接用暴力枚举。

　　下面给出用位运算与状态压缩的做法，时间复杂度是$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 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 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<PII> ret(N);
35     for (int i = 0; i < 1 << 16; i++) {
36         int t = state;
37         vector<PII> 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 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 typedef pair<int, int> PII;
 8 
 9 const int N = 10;
10 
11 vector<PII> 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 #include <cstdio>
 2 #include <string>
 3 #include <queue>
 4 #include <unordered_map>
 5 #include <algorithm>
 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/