AcWing 116. 飞行员兄弟
原题链接
简单
作者:
Coding酥
,
2024-02-20 09:06:37
,
所有人可见
,
阅读 41
#include<iostream>
#include<algorithm>
#include<utility>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 5;
char g[N][N], backup[N][N];
//vector<PII> st;
void turn_one(int x, int y){
if(g[x][y] == '+') g[x][y] = '-';
else g[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 get(int x, int y){
return x * 4 + y;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
// 读取开关
for(int i = 0; i < 4; i++) cin >> g[i];
vector<PII> st;
// 遍历每个位置开关
for(int op = 0; op < 1 << 16; op++){
vector<PII> stup;
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){
stup.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(g[i][j] == '+') {
close = true;
break;
}
if(!close){
if(st.empty() || stup.size() < st.size()) st = stup;
}
memcpy(g, backup, sizeof g); // 还原
}
cout << st.size() << endl;
for(auto it : st) cout << it.first+1 << " " << it.second+1 << endl;
return 0;
}