题目描述
blablabla
样例
blablabla
算法1
C++ 代码
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std; //枚举第一行状态,可按可不按 第234行确定,然后看第5行是否全1
int N = 0;
char p[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 X =x + dx[i] ,Y =y + dy[i];
if (X >= 0 && Y >= 0 && Y < 5 && X < 5)
p[X][Y] ^= 1;
}
}
void after() // 每次枚举都会改变原状态必须复制一个
{
int mi = 1000000;
for(int i=0; i < (1 << 5); i++)
{
int res = 0; bool isok = true;
char copy[10][10];
memcpy( copy, p, sizeof copy);
for(int j=0; j < 5 ;j++)
if(i >> j &1)
{
res++;
turn (0,j); //第j个点按下,其周围的都要变化
}
for(int j=1; j < 5 ;j++) //第二三四行
for(int k=0; k < 5; k++)
if(p[j-1][k] == '0') //该行要不要按下根据上一行的点
{
res++;
turn(j,k);
}
for(int k=0; k < 5; k++)
{
if(p[4][k] != '1') //失败
{isok = false; //N = -1;
break;}
}
if(isok)
mi = min(res , mi);
memcpy( p,copy, sizeof p);
}
if(mi <= 6) //枚举完所有次数,最小次数<=6的说明可以
N = mi;
else N = -1;
}
int main()
{
int n; cin >> n;
while(n--)
{
for(int i=0; i < 5; i++)
{
cin >> p[i];
}
after();
cout << N<< endl;
}
return 0;
}
`