AcWing 95. 费解的开关
原题链接
中等
作者:
拾心
,
2024-03-27 22:15:40
,
所有人可见
,
阅读 2
/*
要把所有灯按亮,不一定是通过按下这盏灯按亮的,有可能是按别的灯,顺带把这个灯按亮
所以我们固定住第一行--通过枚举对第一行32种状态的按法,32中状态一定包含了所以可能
1.每次先固定第一行的是否按 按哪些的状态
2.然后对媒介第一到第四行 对当前行某个位置暗的灯 按下下一行的灯 将其点亮
3.最后去判断最后一行 看看是否满足全部灯亮的情况
*/
#include <iostream>
#include <cstring>
using namespace std;
int n;
char g[10][10], backup[10][10];
int dx[] = { 1,-1,0,0,0 };
int dy[] = { 0,0,-1,1,0 };
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;//0变1 1变0
}
}
int main()
{
cin >> n;
while (n--)
{
for (int i = 0; i < 5; i++)
cin >> g[i];
int ans = 1e9;
for (int k = 0; k < 32; k++)//二进制表示 1表示要按的位置---,
{
memcpy(backup, g, sizeof g);
int cnt = 0;
for (int j = 0; j < 5; j++)
{
if (k >> j & 1)
{
cnt++;
turn(0, j);
}
}
for (int i = 0; i < 4; i++)
{
for (int j = 0; j <= 5; j++)
{
if (g[i][j] == '0')
{
cnt++;
turn(i+1, j);
}
}
}
int flag = 0;
for (int i = 0; i < 5; i++)
{
if (g[4][i] == '0')
{
flag = 1;
break;
}
}
if (!flag)ans = min(ans, cnt);
memcpy(g, backup, sizeof backup);
}
if (ans > 6)cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}