题目描述

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

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

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

01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：

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

输入样例

00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例

3
2
-1

注意点

①：每个位置只会操作一次，如果对每个位置操作两次，则当前的开关和其周围的开关会回到最初始状态，而要求计算最少的操作次数，所以一个位置只会操作一次
②：当一行的开关的状态确定以后，那么根据第一行的状态就可以对第二行的开关进行操作，以此类推，直到最后一行开关，当最后一行的开关全为1时，说明可以将所有的开关打开
③：最开始读入的第一行并不是初始状态，虽然固定第一行的状态之后可以确定第二行的操作，但是你并不能保证，你不对第一行进行操作，对第一行进行操作之后就是初始状态，这时候就可以对其进行固定。第一行有五个开关，对每一个开关都有两种选择(开或者关)，所以总共有$2^5$种操作

时间复杂度 O($2^5$×20×5×500)

第一行开关可以对其进行$2^5$种操作；操作之后第一行的状态就确定了，然后每次都是固定上一行，确定下一行的操作，所以只有4行，每行5个开关，所以4×5；每一个位置的开关都会影响它本身和周围的开关，所以为5；最多有500组测试数组，因此得到上面的时间复杂度

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;
char light[10][10];
char backup[10][10];//备份数组
int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0};//上、下、左、右、中五个位置
void turn(int x,int y){
    for(int i=0;i<5;i++){
        int a=x+dx[i],b=dy[i]+y;
        if(a>=0&&a<5&&b>=0&&b<5)
        light[a][b]^=1;//字符0的ascii码为48(00011000)，字符1的ascii码为49(00011001) 两者之间的互换只需要异或上1即可
    }
}
int work(){
    int res=10;
    /*
    对第一行总共有32种操作 每一次循环的k就是一次操作
    比如说 k=00001,表示将第一行最后一个开关按一下
    k=001010,表示将第一行第三个开关和第四个开关按一下
    */
    for(int k=0;k<1<<5;k++){
        int cnt=0;
        memcpy(backup,light,sizeof light);//备份数组的目的是下面的循环会对读入light[][]进行操作，但是每次循环又需要回到最初light[][]状态
        for(int i=0;i<5;i++){//这个循环是不断的向右移位，如果移到某一位的为1，表示要对这个开关按一下
            if(k>>i&1) {
                turn(0,i);
                cnt++;
            }
        }
        for(int i=0;i<4;i++){//这两重循环是，固定当前行固定，对下一行进行操作
            for(int j=0;j<5;j++){
                if(light[i][j]=='0'){
                    turn(i+1,j);
                    cnt++;
                }
            }
        }
        bool flag=true;
        for(int i=0;i<5;i++)//最后访问最后一行，如果最后一行的开关全为1，则操作成功，否则失败
            if(light[4][i]=='0'){
                flag=false;
                break;
            }
        if(flag) res=min(cnt,res);//操作成功的前提下，更新res，最终res里面存放的是32种情况下的最小值
        memcpy(light,backup,sizeof light);//
    }
    if(res>6) return -1;
    return res;
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        for(int i=0;i<5;i++) scanf("%s",light[i]);
        printf("%d\n",work());
    }
    return 0;
}