AcWing 95. 费解的开关
原题链接
中等
作者:
我是java同学
,
2023-01-03 15:16:18
,
所有人可见
,
阅读 145
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 10000;
char g[10][10];
int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {0, 0, 1, 0, -1};
void turn(int x, int y)
{
for (int i = 0; i < 5; i ++)
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 5 && b >= 0 && b < 5)
{
g[a][b] ^= 1;
}
}
}
int work()
{
int ans = INF;
for (int k = 0; k < 1 << 5; k ++)
{
char backup[10][10];
memcpy(backup, g, sizeof g);
int res = 0;
for (int j = 0; j < 5; j ++)
{
if (k >> j & 1)
{
res ++;
turn(0, j);
}
}
for (int i = 0; i < 4; i ++)
for (int j = 0; j < 5; j ++)
if (g[i][j] == '0')
{
res ++;
turn(i + 1, j);
}
bool is_successful = true;
for (int j = 0; j < 5; j ++)
if (g[4][j] == '0')
{
is_successful = false;
break;
}
if (is_successful) ans = min(ans, res);
memcpy(g, backup, sizeof g);
}
if (ans > 6) return -1;
else return ans;
}
int main()
{
int T;
cin >> T;
while (T -- )
{
for (int i = 0; i < 5; i ++) cin >> g[i];
cout << work() << endl;
}
return 0;
}