每次看别人题解时,一堆dqwdaf字母形式命名的变量,就让人头疼,每看一行,都要停下来去想变量的语义。
现在我用纯中文语义定义变量,看起来应该会稍微易读一点吧
已在acwing的oj上Ac
java代码
import java.util.Scanner;
//详细解释见 yxc自己录的视频 https://www.acwing.com/video/754/
/*要说明的是
第一行的每一种亮灭方案,都会导致第一行锁定后 后续的按法不同,所以需要把第一行的所有亮灭情况进行枚举。
锁定完第一行之后,后面只需要对应即可,然后辐射效果也假定为只辐射一次
1
10001
11011
11111
11111
11111
* */
public class Main {
static int 无解=-1;
public static boolean 全亮(int [][]map){
for(int i=1;i<=5;i++){
for (int j=1;j<=5;j++){
if(map[i][j]==0) return false;
}
}
return true;
}
// 1~5都算合法
public static boolean 范围合法(int i,int j){
if(i>=1&&i<=5&&j>=1&&j<=5) return true;
else return false;
}
public static void 按下该处的灯然后辐射一次(int [][]map, int i, int j){
//i-1排被假设为锁定了
map[i][j]^=1;
map[i-1][j]^=1;
if(范围合法(i,j-1))map[i][j-1]^=1;
if(范围合法(i,j+1))map[i][j+1]^=1;
if(范围合法(i+1,j))map[i+1][j]^=1;
}
public static void 复制数组(int [][]被复制,int [][]复制者){
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
被复制[i][j]=复制者[i][j];
}
}
}
public static int 最少点按次数; //第一行的第_个元素==1 代表 第一行的第1个元素
public static void dfs第一行的亮灭情况(int [][]灯的状态,int 第一行的第_个元素,int 本次方案的点按次数){
//一次都不用按的时候,就已经全亮的情况
if(全亮(灯的状态)&&第一行的第_个元素==1) {
最少点按次数=0;
return;
}
//收尾
if(第一行的第_个元素>5){
for(int m=1;m<=4;m++){
for(int n=1;n<=5;n++){
if(灯的状态[m][n]==0) {
按下该处的灯然后辐射一次(灯的状态,m+1,n);
本次方案的点按次数++;
if(本次方案的点按次数>6) break;
}
}
if(本次方案的点按次数>6) break;
}
if(全亮(灯的状态)) {//准备更新答案
if(本次方案的点按次数!=0) {//收集到有效答案了
if(最少点按次数!=-1){//不是第一次更新min值了
if(本次方案的点按次数<最少点按次数) 最少点按次数=本次方案的点按次数;
}else {//第一次更新min值
//但是不是说第一次就能随便放的,也要保证 点按次数<=6
if(本次方案的点按次数<=6) 最少点按次数=本次方案的点按次数;
}
}
}
return;
}
//不按
int [][]临时保存数组=new int[6][6];
复制数组(临时保存数组,灯的状态);
dfs第一行的亮灭情况(灯的状态,第一行的第_个元素+1,本次方案的点按次数);
复制数组(灯的状态,临时保存数组);
//按
int [][]临时保存数组2=new int[6][6];
复制数组(临时保存数组2,灯的状态);
按下该处的灯然后辐射一次(灯的状态,1,第一行的第_个元素);
dfs第一行的亮灭情况(灯的状态,第一行的第_个元素+1,本次方案的点按次数+1);
复制数组(灯的状态,临时保存数组2);
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int N=in.nextInt();
for(int i=0;i<N;i++) {
int [][]灯状态=new int[6][6];
for(int m=1;m<=5;m++) {
String 一行=in.next();
for(int n=1;n<=5;n++) {
灯状态[m][n]=一行.charAt(n-1)-'0';
}
}
最少点按次数=无解;
dfs第一行的亮灭情况(灯状态,1,0);
System.out.println(最少点按次数);
}
}
}