飞行员兄弟游戏

题目描述

"飞行员兄弟"这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个 $4 \times 4$ 的矩阵，您可以改变任何一个位置 $[i,j]$ 上把手的状态。

但是，这也会使得第 $i$ 行和第 $j$ 列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式

输入一共包含四行，每行包含四个把手的初始状态。

符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式

第一行输出一个整数 $N$，表示所需的最小切换把手次数。

接下来 $N$ 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

输入输出样例 #1

输入 #1

-+--
----
----
-+--

输出 #1

6
1 1
1 3
1 4
4 1
4 3
4 4

输入输出样例 #2

输入 #2

++++
++++
++++
++++

输出 #2

0

限制条件

• $1 \le i, j \le 4$
• 至少有一个把手初始状态是关闭的

样例解释 #1

初始状态：

- + - -
- - - -
- - - -
- + - -

操作序列：

1. 切换 (1,1)：第1行和第1列所有把手状态改变
2. 切换 (1,3)：第1行和第3列所有把手状态改变
3. 切换 (1,4)：第1行和第4列所有把手状态改变
4. 切换 (4,1)：第4行和第1列所有把手状态改变
5. 切换 (4,3)：第4行和第3列所有把手状态改变
6. 切换 (4,4)：第4行和第4列所有把手状态改变

最终所有把手都变为打开状态（-）。

解题思路

这是一个经典的位运算+枚举问题：

1. 将 $4 \times 4$ 的矩阵看作一个 16 位的二进制数，+（闭合）为 1，-（打开）为 0
2. 每个操作 $(i,j)$ 会改变第 $i$ 行和第 $j$ 列的所有位置，包括 $(i,j)$ 本身被改变了两次（等价于改变一次）
3. 实际上，操作 $(i,j)$ 会改变：
   • 所有 $(i, k)$，$k = 1..4$
   • 所有 $(k, j)$，$k = 1..4$
   • 其中 $(i,j)$ 被改变了两次，效果相当于不变，所以需要额外再改变一次
4. 等价于：操作 $(i,j)$ 会改变第 $i$ 行和第 $j$ 列的所有位置，但 $(i,j)$ 被改变了奇数次（1次），其他位置被改变了偶数次（2次）
5. 更准确地说：操作 $(i,j)$ 会切换以下位置的状态：
   • $(i,1), (i,2), (i,3), (i,4)$
   • $(1,j), (2,j), (3,j), (4,j)$
   • 总共 7 个位置（$(i,j)$ 只算一次）

由于只有 $4 \times 4 = 16$ 个位置，可以枚举所有可能的操作组合（$2^{16} = 65536$ 种可能），检查哪种组合能使所有把手打开，并记录最小操作次数。

如果有多种方案操作次数相同，按照题目要求的优先级选择：

• 整体从上到下：先处理行号小的操作
• 同行从左到右：行号相同时，先处理列号小的操作