AcWing 116. 飞行员兄弟
原题链接
简单
作者:
正在努力的ac
,
2025-02-05 00:00:41
,
所有人可见
,
阅读 1
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
//宏定义,坐标
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 5;
char g[N][N], backup[N][N];
int get(int x, int y) {
return x * 4 + y;//4 * 4的矩阵(0 ~ 15)
}
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 main() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cin >> g[i][j];
}
}
vector<PII> res;
//枚举所有情况,右移(表示2^16)
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++) {
//判断当前情况16位2进制数的当前位是否为1
if (op >> get(i, j)& 1) {
temp.push_back({i ,j});//存储横纵坐标
turn_all(i , j);
}
}
}
bool has_closed = false;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (g[i][j] == '+') {
has_closed = true;
}
}
}
if (!has_closed) {
if (res.empty() || res.size() > temp.size()) res = temp;
}
memcpy(g, backup, sizeof g);
}
cout << res.size() << endl;
for (auto op : res) {
cout << op.x + 1 << " " << op.y + 1 << endl;
}
return 0;
}