AcWing 116. 飞行员兄弟
原题链接
简单
作者:
风起于浮萍之末
,
2024-02-13 22:13:18
,
所有人可见
,
阅读 29
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define x first
// 用 x代替first
#define y second
// 用y代替second
using namespace std;
typedef pair<int, int> PII;
const int N = 5;//char 字符还需存储\0
char g[N][N], backup[N][N];// 输入数组和备份数组 因为需要对数组进行多次操作,但是不能修改
int get(int x, int y)// 二维转化为1维
{
return x * 4 + y;
}
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 ++ ) cin >> g[i];
vector<PII> res;
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 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 == false)
{
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;
}