AcWing 95. 费解的开关
原题链接
中等
作者:
lencit
,
2023-11-28 10:53:42
,
所有人可见
,
阅读 43
两个性质:
1个开关最多按一次
按的顺序无关,只和叠加的次数有关
1.固定下第一行的开关状态后->第一行灯也固定->要式所有灯亮->第一行灯亮是必要条件
->能控制第一行的灯只有第二行->第二行的开关固定->....
2.最后检查最后一行是否全亮,全亮则更新结果
本质是第一行开关确定后则整个棋盘开关情况确定
共2^5种方案,按二进制枚举,0->2^5-1,1表示这个开关按
import java.util.*;
public class Main{
static int n;
static int [][] dire={{1,0},{-1,0},{0,1},{0,-1}};
static int [][] map=new int[8][8];
static int [][] backup=new int[8][8];
static boolean check(){
for (int i=0;i<=4;i++){
if (backup[4][i]==0) return false;
}
return true;
}
static void change(int x,int y,int [][] a){
a[x][y]= a[x][y]==0? 1:0;
for (int i=0;i<4;i++){
int nx=x+dire[i][0];
int ny=y+dire[i][1];
if (nx>=0&&nx<5&&ny>=0&&ny<5){
a[nx][ny]= a[nx][ny]==0? 1:0;
}
}
}
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
scan.nextLine();
while(n-->0){
for (int i=0;i<5;i++) {
String[] s = scan.nextLine().split("");
for (int j = 0; j < 5; j++) {
map[i][j] = Integer.parseInt(s[j]);
}
}
int res=8;
for (int i=0;i<1<<5;i++){
for (int j=0;j<5;j++){
for (int k=0;k<5;k++){
backup[j][k]=map[j][k];
}
}
int cnt=0;
for (int j=0;j<5;j++){
if (((i>>j)&1)!=0) {
change(0,4-j,backup);
cnt++;
}
}
//这里二进制的每一位可以看成“向右移动j位得到的位”
for (int j=1;j<=4;j++){
for (int k=0;k<=4;k++){
if (backup[j-1][k]==0) {
change(j,k,backup);
cnt++;
}
}
}
if (check())res=Math.min(res,cnt);
}
System.out.println(res>6 ? -1:res);
if(n!=0)scan.nextLine();
}
}
}