（开关问题）（枚举）（模拟）（位运算）116. 飞行员兄弟
目录
题目链接
一些话
切入点
流程
套路
ac代码
题目链接
116. 飞行员兄弟 - AcWing题库
我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草
一些话
我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草
切入点
// 开关问题，每个开关只按一次，顺序不重要
每个开关都可能被按，下一层的开关不影响到上一层，就可以递推，除了递推还可以枚举所有开关的按法：用位运算
// 思路复杂，操作繁琐，模拟题
求满足条件的情况，枚举时储存
我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草
流程
求符合条件的方案，字典序和全打开，直接从0开始枚举，步数严格小的才储存方案，空方案则储存
因为开关会影响到上下左右的开关，所以不能一层一层递推
// 图较小，用2e16个数转化为矩阵，每个数位表示开关的操作与否、
// 读入部分，直接读入字符数组
// get函数，输入i，j return i * 4 + j
// turn _ont函数，是+就变成-,反之则＋
// turn_all 函数，循环turnone，最后turn_one中心点
// doit函数：枚举1-1<< 16-1,备份数组，一重循环枚举二进制的数位，是1则根据当前的j获取对应的x，y，turn_all(x,y)，把x,y压入vector遍历数组检查是否全关
// 是的话比较vector元素个数和res，严格少则替换，或者res空则替换
// 输出部分：遍历res，输出元素+1
套路
1.一维数模拟二维数组
前提条件表示一个只有01或其他两种元素的矩阵n*m矩阵，开关问题
利用位运算，用2^n*m个整数来表示一个只有01或其他两种元素的矩阵n*m矩阵
for(int op = 0;op < 1 << 16;op++)
运用：可以通过这个来枚举开关问题的解法
2.……
for(auto t: res) cout << t.first + 1 << " " << t.second + 1 << endl;
ac代码
// 19：55 - 20 ：06 想
// 06 ~ 24 wa
// 24!30看答案
// 30~37看题解，不理解turnall是啥，get和位运算
// 开关问题，每个开关只按一次，顺序不重要
// 码量大，操作繁琐，模拟题
// 求符合条件的方案，字典序和全打开，直接从0开始枚举，步数严格小的才储存方案，空方案则储存
// 因为开关会影响到上下左右的开关，所以不能一层一层递推
// 图较小，用2e16个数转化为矩阵，每个数位表示开关的操作与否、
// 读入部分，直接读入字符数组
// get函数，输入i，j return i * 4 + j
// turn _ont函数，是+就变成-,反之则＋
// turn_all 函数，循环turnone，最后turn_one中心点
// doit函数：枚举1-1<< 16-1,备份数组，一重循环枚举二进制的数位，是1则根据当前的j获取对应的x，y，turn_all(x,y)，把x,y压入vector遍历数组检查是否全关
// 是的话比较vector元素个数和res，严格少则替换，或者res空则替换
// 输出部分：遍历res，输出元素+1
#include
#include
#include
#include
#include
using namespace std;
typedef pairPII;
const int N = 5;
char g[N][N],backup[N][N];
vectorres;
int get(int i,int j){return i * 4 + j;}void turn_one(int i,int j){if(g[i][j] == '+') g[i][j] = '-';else g[i][j] = '+';}
void turn_all(int x,int y){for(int i = 0;i < 4;i++){turn_one(i,y);turn_one(x,i);}turn_one(x,y);
}
void input(){for(int i = 0;i < 4;i++){cin >> g[i];}
}
void doit(){for(int op = 0;op < 1 << 16;op++){vectortemp;memcpy(backup,g,sizeof g);for(int i = 0;i < 4;i++){for(int j = 0;j < 4;j++){if(op >> get(i,j) & 1){temp.push_back({i,j});turn_all(i,j);}}}bool flag = true;for(int i = 0;i < 4;i++){for(int j = 0;j < 4;j++){if(g[i][j] == '+') {flag = false;}}}if(flag){if(res.empty() || res.size() > temp.size()) res = temp;}memcpy(g,backup,sizeof g);}
}
void output(){cout << res.size() << endl;for(auto t: res) cout << t.first + 1 << " " << t.second + 1 << endl;
}
int main(){input();doit();output();return 0;
} 我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！