AcWing 95. 费解的开关
原题链接
中等
作者:
hxzz
,
2021-09-03 15:10:54
,
所有人可见
,
阅读 244
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
char g[5][5];
int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {1, 0, 0, -1, 0};
void turn(int x, int y) {
for (int i = 0; i < 5; ++ i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 5 || ny >= 5 || nx < 0 || ny < 0) continue;
g[nx][ny] ^= 1;
}
}
int sovle() {
int ans = 1e7;
for (int i = 0; i < 1 << 5; ++ i) { // 枚举第一行所有可能按的结果
int res = 0;
char cp[5][5];
memcpy(cp, g, sizeof g);
for (int j = 0; j < 5; ++ j) {
if (i >> j & 1) {
turn(0, j);
res ++;
}
}
for (int j = 0; j < 4; ++ j)
for (int k = 0; k < 5; ++ k)
if (g[j][k] == '0')
turn(j + 1, k), res ++;
bool flag = true;
for (int j = 0; j < 5; ++ j)
if (g[4][j] == '0') {
flag = false;
break;
}
if (flag) ans = min(res, ans);
memcpy(g, cp, sizeof cp);
}
if (ans > 6) return -1;
return ans;
}
int main() {
int t;
cin >> t;
while(t --) {
for (int i = 0; i < 5; ++ i)
cin >> g[i];
cout << sovle() << endl;
}
return 0;
}