题目
“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个 的矩阵，您可以改变任何一个位置 上把手的状态。
但是，这也会使得第 行和第 列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行，每行包含四个把手的初始状态。
符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数 ，表示所需的最小切换把手次数。
接下来 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围
输入样例：
-+--
----
----
-+--
输出样例：
6
1 1
1 3
1 4
4 1
4 3
4 4
解题
方法一：枚举 位运算
思路
本题相对于【位运算, 递推】费解的开关来说，每个开关会影响到的范围更大，也就导致递推比较难找出思路，但是本题只有 个开关，而每个开关只有 开/关 两个状态，也就是说操作开关的所有状态数量只有 个，那么我们就可以枚举这 个状态并检查其是否可行，如果可行就更新最优方案。
关于字典序的问题：
我们枚举出的状态转为矩阵的时候是按照这样的顺序把每一位转换的：
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
这样一来，字典序最小就需要保证枚举两个 相同的状态时要先枚举 靠前的状态，而我们从 枚举到 （从小到大）时默认就会优先枚举 靠前的状态，所以按照这种思路解题不需要特殊处理字典序，直接做就行。
注意：每次枚举新的状态操作之前时要先恢复所有开关的初始状态。
代码
import java.util.*;
import java.io.*;
public class Main {
static int N = 4;
static boolean[][] g = new boolean[N][N];
static int ans = 17;
static List<int[]> ansPath = new ArrayList<>();
static void turn(int x, int y) {
g[x][y] = !g[x][y];
for (int i = 0; i < N; ++i) {
g[x][i] = !g[x][i];
g[i][y] = !g[i][y];
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
boolean[][] bak = new boolean[N][N];
for (int i = 0; i < N; ++i) {
String s = in.readLine();
for (int j = 0; j < N; ++j) bak[i][j] = s.charAt(j) == '-';
}
outer: for (int i = 0; i < 1 << 16; ++i) {
int cnt = 0;
List<int[]> path = new ArrayList<>();
for (int j = 0; j < N; ++j) g[j] = bak[j].clone();
for (int j = 0; j < 16; ++j) {
if ((i >> j & 1) == 1) {
turn(j / N, j % N);
path.add(new int[]{j / N + 1, j % N + 1});
++cnt;
}
}
for (int x = 0; x < N; ++x) {
for (int y = 0; y < N; ++y) {
if (!g[x][y]) continue outer;
}
}
if (cnt < ans) {
ans = cnt;
ansPath = path;
}
}
System.out.println(ans);
for (int[] a : ansPath) System.out.printf("%d %d\n", a[0], a[1]);
}
}
位运算优化：
用一个整数代替二维数组，用异或运算代替反转开关状态操作。
import java.util.*;
import java.io.*;
public class Main {
static int N = 4;
static int g, t = (1 << 16) - 1;
static List<int[]> ans = new ArrayList<>();
static int conv(int x, int y) {
return x * N + y;
}
static void turn(int x, int y) {
g ^= 1 << conv(x, y);
for (int i = 0; i < N; ++i) {
g ^= 1 << conv(x, i);
g ^= 1 << conv(i, y);
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int bak = 0;
for (int i = 0; i < N; ++i) {
String s = in.readLine();
for (int j = 0; j < N; ++j) {
if (s.charAt(j) == '-') bak |= 1 << conv(i, j);
}
}
outer: for (int i = 0; i < 1 << 16; ++i) {
List<int[]> path = new ArrayList<>();
g = bak;
for (int j = 0; j < 16; ++j) {
if ((i >> j & 1) == 1) {
int x = j / N, y = j % N;
turn(x, y);
path.add(new int[]{x + 1, y + 1});
}
}
if (g == t && (ans.isEmpty() || path.size() < ans.size())) ans = path;
}
System.out.println(ans.size());
for (int[] a : ans) System.out.printf("%d %d\n", a[0], a[1]);
}
}
评论区