核心思想
这个问题的核心在于找到一个有效的操作序列,这个序列能够将所有的把手从初始状态(一些是 ‘+’,一些是 ‘-‘)转变到目标状态(所有把手都是 ‘-‘)。在这个过程中,每当你翻转一个把手,不仅这个把手的状态会改变,同它在同一行和同一列的所有把手的状态也会随之改变。
操作序列的枚举
为了找到这样的操作序列,代码使用了一种称为“位掩码”的技术来枚举所有可能的操作序列。这里的 op
变量是一个从 0 到 2^16 - 1
的整数,代表了所有可能的操作组合。op
的每一位(共 16 位,对应于 4x4 矩阵中的 16 个把手)表示是否需要对相应的把手进行操作。
翻转操作的决定
对于每一个可能的 op
值,代码通过以下这行来检查每一个把手是否需要被翻转:
if ((op >> i & 1) == 1) {
这里发生了两件事:
op >> i
:将op
向右移动i
位。这个操作的效果是将op
的第i
位移动到最低位的位置。& 1
:然后将移动后的结果与 1 进行“按位与”操作。这将会屏蔽掉除了最低位之外的所有位。因此,如果最低位是 1,这个表达式的结果就是 1;如果最低位是 0,结果就是 0。
解释
所以,if ((op >> i & 1) == 1)
这行代码的意思是:“检查在当前的操作组合 op
中,第 i
个把手是否需要被翻转”。如果需要(即第 i
位是 1),那么代码就会执行 turn(x, y)
方法来翻转位于 x
行 y
列的把手,以及与之在同一行和同一列的所有把手。
这里的 x
和 y
是通过 i
计算得到的,代表了在 4x4 矩阵中的行和列:
import java.io.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
// 定义矩阵大小常量 N 为 4,代表一个 4x4 的矩阵
static final int N = 4;
// 定义一个二维数组 g 来存储当前的矩阵状态
static char[][] g = new char[N][N];
// 定义一个二维数组 backup 来备份原始矩阵状态,以便每次尝试不同的操作时可以重置状态
static char[][] backup = new char[N][N];
// 定义一个字符串 end 用来存储最终操作的序列
static String end = "";
// 定义一个整数 res 来记录最少需要的步骤数,初始值设为最大整数,以便于后续寻找更小的步骤数
static int res = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
// 读入原始矩阵状态
for (int i = 0; i < N; i++ ) {
backup[i] = in.readLine().toCharArray();
}
// 遍历所有可能的操作组合,1 << 16 表示总共有 2^16 种操作组合(每个把手可以是两种状态)
for (int op = 0; op < 1 << 16; op++ ) {
int step = 0;
String str = "";
// 重置矩阵状态到原始状态
for (int j = 0; j < N; j++ ) {
g[j] = backup[j].clone();
}
// 遍历每一种可能的操作,i 表示在 4x4 矩阵中的第 i 个位置
for (int i = 0; i < 16; i++ ) {
// 检查第 i 位是否需要进行操作,(op >> i & 1) == 1 表示第 i 位为 1,需要操作
if ((op >> i & 1) == 1) {
int x = i / N; // 计算行号
int y = i % N; // 计算列号
turn(x, y); // 执行操作,改变相应的行和列
str += x;
str += y;
step++; // 操作次数加一
}
}
// 检查操作后矩阵的状态,判断是否所有把手都已经打开
boolean flag = true;
for (int i = 0; i < N; i++ ) {
for (int j = 0; j < N; j++ ) {
if (g[i][j] == '+') {
flag = false; // 如果还有把手未打开,标记为 false
break;
}
}
}
// 如果所有把手都已经打开,并且当前操作次数小于之前记录的最小操作次数
if (flag) {
if (step < res) {
res = step; // 更新最小操作次数
end = str; // 更新操作序列
}
}
}
// 输出结果
System.out.println(res);
for (int i = 0; i < end.length(); i++ ) {
// 将字符转换为数字,并打印行号和列号,注意字符转数字需要减去 '0' 的 ASCII 值
int a = end.charAt(i) - '0';
int b = end.charAt(i + 1) - '0';
System.out.println((a + 1) + " " + (b + 1)); // 输出时行号和列号从 1 开始,所以需要加 1
i++;
}
}
// turn 方法用于切换指定位置的把手状态,同时也会切换同行同列的把手状态
private static void turn(int x, int y) {
for (int i = 0; i < N; i++ ) {
g[i][y] = g[i][y] == '+' ? '-' : '+'; // 切换列
}
for (int i = 0; i < N; i++ ) {
g[x][i] = g[x][i] == '+' ? '-' : '+'; // 切换行
}
// 切换回指定位置的把手状态,因为它被切换了两次
g[x][y] = g[x][y] == '+' ? '-' : '+';
}
}