AcWing 95. 费解的开关 java
原题链接
中等
作者:
M._3
,
2021-12-16 18:46:32
,
所有人可见
,
阅读 250
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static int n,N=6;
static char a[][]=new char [N][N],b[][]=new char [N][N];
static Scanner sc=new Scanner(System.in);
public static void main(String args[]){
n=sc.nextInt();
while((n--)>0)
{
int res=10;
for(int i=0;i<5;++i)
{
a[i]=sc.next().toCharArray();
}
for(int i=0;i<(1<<5);++i)
{
int step=0;
for(int j=0;j<5;++j)
{
b[j]=Arrays.copyOf(a[j], 5);
}
for(int j=0;j<5;++j)
{
if(((i>>j)&1)==1)
{
step++;
turn(0,j);
}
}
for(int k=1;k<5;++k)
{
for(int u=0;u<5;++u)
{
if(b[k-1][u]=='0')
{
step++;
turn(k,u);
}
}
}
boolean flag=false;
for(int k=0;k<5;++k)
{
if(b[4][k]=='0')flag=true;
}
if(flag==false)
{
res=Math.min(step, res);
}
}
if(res<=6)System.out.println(res);
else System.out.println(-1);
}
}
static void turn(int i,int j)
{
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
b[i][j]=(b[i][j]=='0')?'1':'0';
for(int k=0;k<4;++k)
{
int ix,iy;
ix=i+dx[k];
iy=j+dy[k];
if(ix>=0&&ix<5&&iy>=0&&iy<5){
b[ix][iy]=(b[ix][iy]=='0')?'1':'0';
}
}
}
}