费解的开关 Javaqq44844588的博客-

第一次写题解，求大家多点包容啊，有什么不足欢迎大家批评指正
费解的开关

你玩过“拉灯”游戏吗？25盏灯排成一个5×5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

10111 01101 10111 10000 11011 

在改变了最左上角的灯的状态后将变成：

01111 11101 10111 10000 11011 

再改变它正中间的灯后状态将变成：

01111 11001 11001 10100 11011 

给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
输入格式

第一行输入正整数n，代表数据中共有n个待解决的游戏初始状态。
以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
输出格式

一共输出n行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。
数据范围

0<n≤500

输入样例：

3 00111 01011 10001 11010 11100  11101 11101 11110 11111 11111  01111 11111 11111 11111 11111  

输出样例：

3 2 -1 

思路
这题是要我们求”最少需要几步才能使所有灯变亮”，那就分成两步：
1.把所有灯变亮 怎么才能把按所有灯变亮呢
2.求所有把灯变亮的方法中，步数最少的那个

再细分一下
1.1 如何把灯全部按亮，我觉得这个跟我高中同学玩的魔方有点类似，首先要知道还原的顺序，我也不知道他们玩魔方的方法正不正规，他们的策略就是一层一层的还原，这道题也是一样，如果没有正确的顺序很容易就会关掉之前的几步开的灯，顺序怎么确定呢？

1.2 我们可以先在草稿本上画一下，就举一个比较普遍的例子，假设第2行第2列的灯是关的，我们有几种方法能让它变亮，很容易可以看得出来5种，它本身以及跟它相连的上下左右的四个灯，but每一个都能按么？答案是否定的，因为我们是有顺序的 如果我们按它本身那么周围四个状态都会改变，这个肯定是不行的，相似的它的左边L和右边R也不行，也会改变包括它和他周围的四个格子的状态！！！！
接下来就剩上面和下面。

1.3 就剩两个两个点了上面和下面两个点 ，假设我们的顺序是从上往下，那么我们是要把第一行全部按亮，
举个例子：第一行五个点 x1 x2 x3 x4 x5假设五个点全为关，我们是不是只能按它们对应的下面的那个点，因为它们上面没有点了，这样排除法 只剩下最后一个
就是按下面 就是说我上面一行的灯泡的状态由其下面一行的灯泡确定如果我按下面的那个灯泡上面那个灯泡就亮，不按就不亮
思考一下我 的顺序是从下往上开始，方法是按上面
跟从上往下，按下面结果一样么突然想到这个，由于本人太懒就不实验了

1.4 从上面的分析可以推出，如果第一行的开的灯泡和关掉的灯泡都已确定，我们就只需要一直往下按就行了，按到前四行的灯泡全亮 ，~~这是可以办到的因为上面一行的灯泡的状态由其下面一行的灯泡确定上面说了~~我们只能确保前四行，第五行不能因为没有第六行了，那么结果也就出来了，我们能操作的都已近操作完了，如果循环结束前四行全部按亮 ，且判断第五行全部为亮且总步数小于6，那么我们就把步数更新一下，一直找到最小的那个。

1.5
只要第一行的状态确定，下面的接着按就行了，第一行五个灯，每个灯有开和关两种状态，我们用1表示要按第一行这个灯0表示不按这个灯，总的就是2的五次方32种可能

第一次写题解有点啰嗦不说了
上代码

 import java.util.Scanner; public class Main { public static void main(String[] args) {         Scanner input=new Scanner(System.in); int N=input.nextInt();         String temp; int map[][]=new int[5][5]; int tempmap[][]=new int[5][5]; //备用数组因为第一行有32中可能，每种可能都会改变map数组，我们为了确保答案的准确性需要还原map int res=9999; while((N--)!=0){ for(int i=0;i<5;i++) {                 temp = input.next();                 res=9999; for (int j = 0; j < 5; j++)                     map[i][j]=temp.charAt(j)-'0';//把char型变为int,存入数组 } dfs(map,tempmap,res); } } public static void dfs(int map[][],int tempmap[][],int res){ for(int i=0;i<(1<<5);i++){ //这里是位运算 2的五次方 直接写32也行 int step=0; //先把map复制一遍等会还原 for(int col=0;col<5;col++){ for(int cow=0;cow<5;cow++){                     tempmap[col][cow]=map[col][cow]; } } for(int j=0;j<5;j++){ if((i>>j&1)==1){ //位运算32种情况每种用5的二进制表示                     step++; //用1表示要按第一行这个灯0表示不按这个灯 turn(0,j,map);// 这里只是确定第一行所以是0，j; } } for(int k=0;k<4;k++){ //只要确定前四行即可 for(int m=0;m<5;m++){ if(map[k][m]==0){                         step++; //上一行只能由下一行来确定 turn(k+1,m,map); } } } int flag=0; //循环结束后判断最后一行是否为亮 for(int m=0;m<5;m++){ if(map[4][m]==0){                         flag=1; break; } } if(flag==0){                     res=Math.min(step,res); } //这里还要把map还原，因为他有32种可能性 for(int k=0;k<5;k++) { for (int m = 0; m < 5; m++) {                     map[k][m]=tempmap[k][m]; } } } if(res>6)             System.out.println(-1); else             System.out.println(res); } public static void turn(int x,int y,int map[][]){ for(int i=0;i<5;i++){ int tempx=x+xx[i]; int tempy=y+yy[i]; if(tempx>=0&&tempx<5&&tempy>=0&&tempy<5){                 map[tempx][tempy]^=1; // 异或运算 写成if(map[x][y]==1) map[x][y]==0这种也行 } } } }