老薛主机wordpress模板/北京网站优化seo

飞行员兄弟

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 $16$ 个把手的冰箱。已知每个把手可以处于以下两种状态之一：打开或关闭。只有当所有把手都打开时，冰箱才会打开。把手可以表示为一个 $4\times 4$ 的矩阵，您可以改变任何一个位置 $[i,j]$ 上把手的状态。但是，这也会使得第 $i$ 行和第 $j$ 列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式

输入一共包含四行，每行包含四个把手的初始状态。
符号 $+$ 表示把手处于闭合状态，而符号 $-$ 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。

输出格式

第一行输出一个整数 $N$，表示所需的最小切换把手次数。接下来 $N$ 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

数据范围

1≤i,j≤4

输入样例：

-+--
----
----
-+--

输出样例：

6
1 1
1 3
1 4
4 1
4 3
4 4

知识点

位运算：

• 开关是否改变 → k>>i&1
• 操作开关（开关状态改变0→1、1→0）→ 与1异或

注：二进制从 $0$ ~ $2^{16}-1$，编号增加的顺序正好是对应位置从上到下、从左到右的顺序

代码

#include<iostream>
#include<algorithm>
#include<vector>using namespace std;typedef pair<int,int> PII;int change[4][4];//change数组存放 需要异或的数int get(int x,int y)
{return x * 4 + y;//下标从0开始
}int main()
{int state = 0;for(int i = 0;i < 4;i ++ ){string line;cin >> line;for(int j = 0;j < 4;j ++ ){if(line[j] == '+')state += (1 << get(i,j));}}//1.将矩阵转换为初始状态statefor(int i = 0;i < 4;i ++ ){for(int j = 0;j < 4;j ++ ){for(int k = 0;k < 4;k ++ ){change[i][j] += 1<<get(i,k);//第i行change[i][j] += 1<<get(k,j);//第j列}change[i][j] -= 1 << get(i,j);}}//2.预处理change数组vector<PII> res;//结果方案for(int k = 0;k < 1<<16 ;k ++ ){int now = state;vector<PII> path;//结果是一系列二元组for(int i = 0;i < 16;i ++ ){//遍历16位 看哪些位为1if(k >> i & 1){//第i位为1int x = i / 4 , y = i % 4;now ^= change[x][y];//改变开关path.push_back({x,y});}}if(!now && (res.empty() || res.size() > path.size())) res = path;//所有位置全为0→打开冰箱  && 当前操作次数更少或者是第一种方案}//3.遍历每种方案  操作开关cout << res.size() <<endl;for(auto p:res) cout << p.first+1 << ' ' << p.second+1 << endl;//输出最佳方案return 0;
}