AcWing 95. 费解的开关
原题链接
中等
作者:
Nmoek
,
2021-01-30 15:53:39
,
所有人可见
,
阅读 283
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char num[10][10];
int m_x[5] = {0, 0, 0, -1, 1};
int m_y[5] = {0,-1, 1, 0, 0};
void turn(int a, int b)
{
for(int i = 0;i < 5;i++)
{
int x = a + m_x[i];
int y = b + m_y[i];
if(x >= 0 && x < 5 && y >= 0 && y < 5)
{
num[x][y] ^= 1;
}
}
}
int work()
{
int ans = 1000000;
for(int i = 0 ;i < 32;i++)
{
char temp[10][10];
memcpy(temp, num, sizeof(num));
int res = 0;
for(int k = 0;k < 5;i++)
{
if(i >> k & 1)
{
res++;
turn(0, k);
}
}
bool flag = true;
for(int n = 0;n < 4;n++)
{
for(int m = 0;m < 5;m++)
{
if(num[n][m] == '0')
{
res++;
turn(n + 1, m);
}
}
}
for(int j = 0;j < 5;j++)
{
if(num[4][j] == '0')
{
flag = false;
break;
}
}
if(flag)
ans = min(res, ans);
memcpy(num, temp, sizeof(num));
}
if(ans > 6)
return -1;
return ans;
}
int main()
{
int n;
scanf("%d", &n);
while(n--)
{
for(int i =0; i< 5;i++)
{
scanf("%s", num[i]);
}
printf("%d\n", work());
}
return 0;
}