“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 $16$ 个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个 $4×4$ 的矩阵，您可以改变任何一个位置 $[i,j]$ 上把手的状态。
但是，这也会使得第 $i$ 行和第 $j$ 列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行，每行包含四个把手的初始状态。
符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数 $N$，表示所需的最小切换把手次数。
接下来 $N$ 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围
$1≤i,j≤4$
输入样例：
输出样例：
1
2
3
4
5
6
7
| 6
1 1
1 3
1 4
4 1
4 3
4 4
|
题目解析
$i, j ∈ [1,4]$，我们发现为了最优性，每个点至多只可能改变一次状态（指自己影响自己），数据点很小，用状态压缩暴力枚举所有点是否自己影响自己即可
若仍对状态压缩有不理解的地方，请回顾 最短Hamilton路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 10;
char a[N][N];
int arr[N][N], Vis[N][N], brr[N][N];
void change(int x, int y) {
brr[x][y] == 1 ? brr[x][y] = 0 : brr[x][y] = 1;
for (int i = 1; i <= 4; i++) {
if(i != x) brr[i][y] == 1 ? brr[i][y] = 0 : brr[i][y] = 1;
if(i != y) brr[x][i] == 1 ? brr[x][i] = 0 : brr[x][i] = 1;
}
}
int main() {
for (int i = 1; i <= 4; i++) {
scanf("%s", a[i] + 1);
}
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if(a[i][j] == '-') {
arr[i][j] = 0;
} else {
arr[i][j] = 1;
}
}
}
for (int k = 0; k < (1 << 16); k++) {
memset(Vis, 0, sizeof(Vis));
int q = 1, p = 0;
for (int i = 0; i < 16; i++) {
p++;
if(i % 4 == 0 && i != 0) q += 1, p = 1;
if(k >> i & 1) {
Vis[q][p] = 1;
} else Vis[q][p] = 0;
}
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
brr[i][j] = arr[i][j];
}
}
int ans = 0;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if(Vis[i][j] == 1) {
ans++;
change(i, j);
}
}
}
int flag = 0;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if(brr[i][j] == 1) { flag = 1; break; }
} if(flag == 1) break;
}
if(flag == 0) {
printf("%d\n", ans);
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if(Vis[i][j] == 1) {
printf("%d %d\n", i, j);
}
}
}
}
} return 0;
}
|