“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有16个把手的冰箱。 已知每个把手可以处于以下两种状态之一：打开或关闭。只有当所有把手都打开时，冰箱才会打开。把手可以表示为一个4х4的矩阵，您可以改变任何一个位置[i,j]上把手的状态。但是，这也会使得第i行和第j列上的所有把手的状态也随着改变。请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行，每行包含四个把手的初始状态。
符号“+”表示把手处于闭合状态，而符号“-”表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数N，表示所需的最小切换把手次数。
接下来N行描述切换顺序，每行输入两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围
1≤i,j≤4
输入样例：
-+--
----
----
-+--
输出样例：
6
1 1
1 3
1 4
4 1
4 3
4 4
思路：
这题相当于费解开关的另一个版本，那题是我第一次写题解，有兴趣的可以看一哈，这一题是我第二次写哈哈哈
具体做法：
每种可能性用16位的二进制表示 每一位的1表示要改变，0表示不改变
首先看成16个格子，0~15这么排开
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
格子的中表示的数分别对应16二进制中的第i个数，看它是0还是1，1表示要改变，0表示不改变
`for (int i = 0; i < 1 << 16; i++) {
//这题数据比较小 把所有的情况全部写出来 2的十六次方
for (int m = 0; m < 4; m++) {
for (int n = 0; n < 4; n++) {
if ((i >> (m * 4 + n) & 1) == 1) //不难发现每行的行列与对应的数字的关系 位运算是1就改变
// 如果对应位数是1就改变其状态
turn(m,n);
}
}
}
举个例子 第一次i=0000 0000 0000 0000
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
第一种情况是全部都不按 ，类似的接下来的几种情况我们也都可以推导出来，总有题目要求有解则说明总有几种情况是可以的
由于我们是从第0位开始，所以我们找到的解法肯定是字典序最小的
还有就是每次判断一个方案是否可行，map数组都会改变，为了答案的准确性我们应该在每次循环后还原数组
然后上代码
import java.util.Scanner;
public class Main {
public static char map[][] = new char[5][5];
public static char maptemp[][] = new char[5][5];//用于还原数组
public static int res[][] = new int[100][3];
static int indexx = 0;
static int ans = 1000;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
for (int i = 0; i < 4; i++) {
String temp = input.next();
for (int j = 0; j < 4; j++) {
map[i][j] = temp.charAt(j);
maptemp[i][j] = map[i][j];
}
}
dfs(map, maptemp, 0);
}
public static void dfs(char map[][], char temp[][], int step) {
int tempx = 0;//用于记录anss数组的长度
int anss[][] = new int[1000][3];//z最后输出的记录每一步的数组
for (int i = 0; i < 1 << 16; i++) {
//这题数据比较小 把所有的情况全部写出来 2的十六次方
for (int m = 0; m < 4; m++) {
for (int n = 0; n < 4; n++) {
if ((i >> (m * 4 + n) & 1) == 1) {
turn(m, n);
step++;
//找一个数组储存走的每一步
res[indexx][0] = m;
res[indexx++][1] = n;
}
}
}
int flag = 0;
//校验把手是否全部打开
for (int m = 0; m < 4; m++) {
for (int n = 0; n < 4; n++) {
if (map[m][n] == '+') {
flag = 1;
break;
}
}
}
//如果打开则更新步数 和坐标数组
if (flag == 0) {
if (ans > step) {
tempx = indexx;
ans = step;
for (int j = 0; j < indexx; j++) {
anss[j][0] = res[j][0];
anss[j][1] = res[j][1];
}
}
}
//还原数组，还原步数，
for (int k = 0; k < 5; k++) {
for (int m = 0; m < 5; m++) {
map[k][m] = temp[k][m];
}
}
step = 0;
indexx = 0;//还原数组长度
}
//输出结果
System.out.println(ans);
for (int i = 0; i < tempx; i++) {
System.out.println((anss[i][0] + 1) + " " + (anss[i][1] + 1));
}
}
public static void turn ( int x, int y){
for (int i = 0; i < 4; i++) {
//x轴上的变
if (map[x][i] == '-') {
map[x][i] = '+';
} else
map[x][i] = '-';
//y轴上的变
if (map[i][y] == '-') {
map[i][y] = '+';
} else
map[i][y] = '-';
}
//由于X轴 Y轴变了两次 x y 等于没变，最后还要变一下
if (map[x][y] == '-')
map[x][y] = '+';
else
map[x][y] = '-';
}
}
~~才开始写题解没有经验，有点乱，希望大家，下手轻点
对了这题是我看y总的视频后才写出来的，y总nb