原题链接
116. 飞行员兄弟
题目难度：简单
题目来源：《算法竞赛进阶指南》
题目描述
“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 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
|
题目分析
这道题也是类似于费解的开关和翻硬币的题目
每次按下开关，会使同一行同一列的开关状态改变，最终将所有开关的状态置为打开的状态
对于所有开关问题的共同点有两个，首先每个开关最多按一次，因为第二次按下等同于没有按，其次结果和按下的顺序是无关的
但是这道题与之前的题目又有不同，因为对于一个开关来说，有一行和一列的开关都会影响到他的状态，因此我们就不能用递推的方法解决这个方法了
我们观察到这个开关的数据量非常小，实际上用最暴力的枚举方法也可以通过这道题
那其实最终的做法就是枚举所有方案（是否按开关），那么我们枚举所有方案，其实只需要从$0$枚举到$2^{16}-1$即可，这里我们把每一个数都可以理解为一个十六位的二进制数，某一位为1的话就是就按下，某一位是0的话就不按，对于每一个方案分别对开关进行操作，最后对结果进行判断，是否满足题目要求，符合条件只需要判断一下步数是否最小即可
对于棋盘我们还是选择使用数组来存储，否则不太容易理解
这里有一个难点在于如何将一个二维数组与一个一维的二进制串建立起一个映射关系，我们其实可以填一个表
示例代码
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
79
80
81
82
83
84
85
86
| #include<iostream>
#include<vector>
#include<memory.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 5;
bool board[N][N], backup[N][N];
int get(int x, int y)
{
return x * 4 + y;
}
void turn_one(int x, int y)
{
board[x][y] = !board[x][y];
}
void turn_all(int x, int y)
{
for (int i = 0; i < 4; i++)
{
turn_one(x, i);
turn_one(i, y);
}
turn_one(x, y);
}
int main()
{
vector<PII> res;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
{
char in;
cin >> in;
if (in == '+')
board[i][j] = false;
else
board[i][j] = true;
}
for (int op = 0; op < (1 << 16); op++)
{
vector<PII> temp;
memcpy(backup, board, sizeof(board));
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (((op >> get(i, j)) & 1) == 1)
{
temp.push_back({ i,j });
turn_all(i, j);
}
}
}
bool close = false;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (board[i][j] == false)
close = true;
if (close == false)
{
if (res.empty() || res.size() > temp.size())
res = temp;
}
memcpy(board, backup, sizeof(backup));
}
cout << res.size() << '\n';
for (auto op : res)
cout << op.x + 1 << ' ' << op.y + 1 << '\n';
return 0;
}
|
