题目链接
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.……<PII>的遍历
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 <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> using namespace std; typedef pair<int,int>PII; const int N = 5; char g[N][N],backup[N][N]; vector<PII>res; 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++){ vector<PII>temp; 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; }