614
发布时间 2023-06-14 16:50:37作者: ManaMouse
#include<bitset>
#define dbg(x) cout<<#x<<"="<<x<<"\n";
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
/*
你玩过“拉灯”游戏吗？
25盏灯排成一个 5×5的方形。
每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1
表示一盏开着的灯，用数字 0
表示关着的灯。
复杂度 500*25^6=1e9需要优化
例如从
1 1 1 1
1 0 ->1 1 需要三步 三步的步骤可以交换。
对于aij 能改变他的点只有上，下两个点。在确定一行的状态，以及上一行的状态后，可以得到下一行。
比如我确定了一行在操作后为01000,那么可以推出来下一行的操作为do undo do do do
因此从第一行开始枚举操作，一共32种操作方式，初态最多有32种。
比如：原来第一行 00111
枚举每个点是否操作
复杂度为500*2^5*5=
*/
bitset<7>bs[7];
bitset<7>b[7];
bool j()
{
for(int i=1;i<=5;++i){
for(int j=1;j<=5;++j){
if(!b[i][j])return false;
}
}
return true;
}
void solve()
{
for(int i=0;i<=6;++i)bs[i]=b[i]=0;
for(int i=1;i<=5;++i){
cin>>bs[i];
bs[i]<<=1;
}
// for(int i=0;i<=6;++i)cout<<bs[i]<<"\n";
int ans=INF;
int op[6];
for(int init=0;init<=31;++init){
int res=0;
for(int i=1;i<=5;++i)
{
b[i]=0;
b[i]|=bs[i];
}
for(int i=0;i<5;++i){
if(init>>i&1)op[i+1]=1;
else op[i+1]=0;
}
for(int j=1;j<=5;++j){
for(int i=1;i<=5;++i){
if(op[i]==1){
b[j-1][i]=~b[j-1][i];
b[j][i-1]=~b[j][i-1];
b[j][i]=~b[j][i];
b[j][i+1]=~b[j][i+1];
b[j+1][i]=~b[j+1][i];
res++;
}
}
for(int i=1;i<=5;++i){
if(b[j][i]==0)op[i]=1;
else op[i]=0;
}
}
if(j())
ans=min(ans,res);
}
if(ans>6)cout<<-1<<"\n";
else cout<<ans<<"\n";
}
int main()
{
int t;cin>>t;
while(t--){
solve();
}
}