你玩过“拉灯”游戏吗?25盏灯排成一个5x5的方形。每一个灯都有一个开关,游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。
给定一些游戏的初始状态,编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
y总的方法,时间复杂度O(n * 2^n),n指矩阵边长,本题为5。
import java.util.Scanner;
public class Main {
static char[][] g = new char[5][5];
static int[] dx = {0,-1,0,1,0}, dy = {0,0,1,0,-1};
static final int INF = 100000;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while(n-- != 0) {
for(int i = 0; i < 5; i++)
g[i] = sc.next().toCharArray();
int res = work();
System.out.println(res);
}
}
static int work() {
int res = INF;
char[][] backup = new char[5][];
//第一排有32种可能翻法,第一排翻完后,剩下的排翻法就固定了;我们只需找出这32种翻法中的最少翻次
for(int k = 0; k < 32; k++) {
int cnt = 0;
//备份初始状态
for(int i = 0; i < 5; i++)
backup[i] = g[i].clone();
//先翻第一排
for(int i = 0; i < 5; i++) {
if((k >> i & 1) == 1) { //注意优先级
turn(0,i);
cnt ++;
}
}
//再翻剩下的4排,由于第一排已经固定,因此每一排翻的时候只需要确保上一排灯全亮即可
for(int i = 0; i < 4; i++)
for(int j = 0; j < 5; j++) {
if(g[i][j] == '0') {
turn(i+1,j);
cnt ++;
}
}
//翻完后只需判断下最后一排,如果最后一排还有不亮的,说明无解
boolean isSuccessful = true;
for(int i = 0; i < 5; i++)
if(g[4][i] == '0') {
isSuccessful = false;
break;
}
if(isSuccessful) res = Math.min(res,cnt);
//恢复初始状态
for(int i = 0; i < 5; i++)
g[i] = backup[i].clone();
}
if(res > 6) return -1;
return res;
}
static void turn(int sx, int sy) {
for(int i = 0; i < 5; i++) {
int x = sx + dx[i];
int y = sy + dy[i];
if(x >= 0 && x < 5 && y >= 0 && y < 5)
g[x][y] ^= 1; //'0' '1' 翻转
}
}
}