AcWing 116. 飞行员兄弟 (二进制枚举就是神!!!)
作者:
冰冷酒
,
2022-02-21 17:30:35
,
所有人可见
,
阅读 287
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 110;
char s[N][N], aa[N][N];
int res = 1e9;
int ans[N], p[N], idx;
void turn(int x, int y) // 每一次的操作
{
for (int i = 1; i <= 4; i ++)
{
if (s[x][i] == '+') s[x][i] = '-';
else s[x][i] = '+';
}
for (int i = 1; i <= 4; i ++)
{
if (i == x) continue;
if (s[i][y] == '+') s[i][y] = '-';
else s[i][y] = '+';
}
}
void out() // debug输出函数
{
for (int i = 1; i <= 4; i ++)
{
for (int j = 1; j <= 4; j ++)
cout << s[i][j] << ' ';
cout << endl;
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for (int i = 1; i <= 4; i ++)
for (int j = 1; j <= 4; j ++)
cin >> aa[i][j];
for (int a = 0; a < (1 << 5); a ++)
for (int b = 0; b < (1 << 5); b ++)
for (int c = 0; c < (1 << 5); c ++)
for (int d = 0; d < (1 << 5); d ++) // 无脑枚举
{
for (int i = 1; i <= 4; i ++)
for (int j = 1; j <= 4; j ++)
s[i][j] = aa[i][j];
int cnt = 0;
idx = 0;
for (int i = 0; i < 4; i ++)
if (a >> i & 1)
{
cnt ++;
turn(1, 4 - i);
p[++ idx] = 1 * 100 + (4 - i);
}
for (int i = 0; i < 4; i ++)
if (b >> i & 1)
{
cnt ++;
turn(2, 4 - i);
p[++ idx] = 2 * 100 + (4 - i);
}
for (int i = 0; i < 4; i ++)
if (c >> i & 1)
{
cnt ++;
turn(3, 4 - i);
p[++ idx] = 3 * 100 + (4 - i);
}
for (int i = 0; i < 4; i ++)
if (d >> i & 1)
{
cnt ++;
turn(4, 4 - i);
p[++ idx] = 4 * 100 + (4 - i);
}
int leap = 0;
for (int i = 1; i <= 4; i ++)
for (int j = 1; j <= 4; j ++)
if (s[i][j] == '+')
leap = 1;
if (!leap)
{
if (res >= cnt)
{
res = cnt;
for (int i = 1; i <= idx; i ++)
ans[i] = p[i];
}
}
}
sort(ans + 1, ans + res + 1);
cout << res << endl;
for (int i = 1; i <= res; i ++)
cout << ans[i] / 100 << ' ' << ans[i] % 100 << endl;
return 0;
}