基础算法题（费解的开关）

果然，暂时做不出的题目其实没必要死磕，可能只是自己的当前的能力还不够，学到了一定的程度之后有些题目自然就更好理解了，特别是对于我们计算机专业，知识体量大。
以上皆是废话！！！

这个题目似乎可以作为搜索和位运算的一个十分典型的题目了。然而对于怎么用位运算我真的十分的弱，orz，orz，orz。目前还没有理解位运算的精髓，所以只能通过其他的方法解题。
思路：一个5x5的矩阵中，每个位置放了一个灯，如果按某个位置的灯的话，这个位置的上下左右的灯都会改变状态（包括它本身），那我们可以知道，我肯定是不能随便去按开关的，我们要按照一定的顺序来进行，我们知道可以观察到如下的规律：
1、按过的灯就不能再按下去了，否则会做无用功。
2、即使这个灯是亮的，它也可能有必要按下去。
3、如果第一行的灯的按的方案都确定下来的话，那么我后续如何按也是确定的。（这一点很难想到），在我看来，其实也不一定是第一行，也可以是第一列，或者是任何一行，或者是任意一列定下来了的话，那么我们这种情况下的按的次数也就确定下来了。只是我们让第一行先确定下来更好写代码。
接着，我们来说说如何写代码：
由于本人不擅长用位运算来解题，主要是菜。所以我们可以枚举第一行的五个位置的每种状态，也就是次，然后对这32次来进行讨论步数，找出最小的步数即可。
那么，我们怎么枚举第一行的每种灯的状态呢？
我们可以用一个dfs，枚举每种灯按和不按的区别，由于我们讨论的是第一行的，所以我们加入要按下这个灯的开关的话，我们就只要改变它的下左右的灯的状态即可，没必要考虑第第一行之前的灯的状态。

c[1][cnt]=!c[1][cnt];
c[2][cnt]=!c[2][cnt];
c[1][cnt-1]=!c[1][cnt-1];
c[1][cnt+1]=!c[1][cnt+1];

但是，我们也不一定要按下这个开关啊，所以我们要回溯不按这个开关的情况。
dfs代码：

void dfs(int cnt,int k){
//这里的cnt指的是枚举到了第几列，而k是指在枚举到了这一列的时候已经按下开关的次数 
    if(cnt>5){
        ans=min(ans,judge(k));
        return;
    }
//注意这里我们是将这个位置下左右（注意不要上的位置）的灯的状态改变，也就代表这个灯我们按下了 
    c[1][cnt]=!c[1][cnt];
    c[2][cnt]=!c[2][cnt];
    c[1][cnt-1]=!c[1][cnt-1];
    c[1][cnt+1]=!c[1][cnt+1];
    dfs(cnt+1,k+1);  //按下的情况 
    c[1][cnt]=!c[1][cnt];  //回溯 
    c[2][cnt]=!c[2][cnt];
    c[1][cnt-1]=!c[1][cnt-1];
    c[1][cnt+1]=!c[1][cnt+1];
    dfs(cnt+1,k);  //不按的情况 
} 

然后当我们枚举到了第5列的情况之后（我们枚举的是第一行的全部5列的按的情况），那么就可以进行验证这种按法是否可行了。
接下来，我们谈谈judge函数的代码：
我们目前已经知道我们第一列这种按法的情况下的已经按下的次数了，接着我们要检查一下这样下去往下递推按下去的总共要按的次数，当然，如果发现这种按法下，最后一行还是有灯亮着的话，那就说明这种按法是无效的。我们只要对前四行执行必要的按与不按的操作，然后检查第五行是否全部亮即可。
这里要注意的一个点是，如果对其他行进行检察的话，加入这个灯是暗的，那么你按开关的位置就是你这个灯的位置的下面那个位置，因为如果你按自身位置的话，你的前一行的灯的状态也会改变。这是不行的。
judge函数代码：

int judge(int k){
    int sum=k;
    for(int i=1;i<=5;i++){  
    //先将目前第一行按后的灯的状态存放在一个临时的数组里面，防止改变原数组 
        for(int j=1;j<=5;j++){
            b[i][j]=c[i][j];
        }
    }
    for(int i=1;i<=4;i++){  //检查前四行 
        for(int j=1;j<=5;j++){
            if(!b[i][j]){  //如果这个位置灯是关的，那么就按一次开关 
                sum++;
            //这里注意我们按的位置其实是这个灯的正下方的那个位置，
            //因为如果你按自身的位置的话，你会改变你这个位置的上一行的灯的状态 
                b[i][j]=!b[i][j];
                b[i+1][j]=!b[i+1][j];
                b[i+1][j-1]=!b[i+1][j-1];
                b[i+1][j+1]=!b[i+1][j+1];
                b[i+2][j]=!b[i+2][j];
            }
        }
    }
    for(int i=1;i<=5;i++){
        if(!b[5][i])  return inf;  //如果最后一行还有暗的灯，那这种第一行按的方法是无效的
    }
    return sum;
}

ac代码：

#include<iostream>
using namespace std;
const int inf=0x3f3f3f;
int c[10][10];
int ans;
int b[10][10];

int judge(int k){
    int sum=k;
    for(int i=1;i<=5;i++){  
    //先将目前第一行按后的灯的状态存放在一个临时的数组里面，防止改变原数组 
        for(int j=1;j<=5;j++){
            b[i][j]=c[i][j];
        }
    }
    for(int i=1;i<=4;i++){  //检查前四行 
        for(int j=1;j<=5;j++){
            if(!b[i][j]){  //如果这个位置灯是关的，那么就按一次开关 
                sum++;
            //这里注意我们按的位置其实是这个灯的正下方的那个位置，
            //因为如果你按自身的位置的话，你会改变你这个位置的上一行的灯的状态 
                b[i][j]=!b[i][j];
                b[i+1][j]=!b[i+1][j];
                b[i+1][j-1]=!b[i+1][j-1];
                b[i+1][j+1]=!b[i+1][j+1];
                b[i+2][j]=!b[i+2][j];
            }
        }
    }
    for(int i=1;i<=5;i++){
        if(!b[5][i])  return inf;
    }
    return sum;
}

void dfs(int cnt,int k){
//这里的cnt指的是枚举到了第几列，而k是指在枚举到了这一列的时候已经按下开关的次数 
    if(cnt>5){
        ans=min(ans,judge(k));
        return;
    }
//注意这里我们是将这个位置下左右（注意不要上的位置）的灯的状态改变，也就代表这个灯我们按下了 
    c[1][cnt]=!c[1][cnt];
    c[2][cnt]=!c[2][cnt];
    c[1][cnt-1]=!c[1][cnt-1];
    c[1][cnt+1]=!c[1][cnt+1];
    dfs(cnt+1,k+1);  //按下的情况 
    c[1][cnt]=!c[1][cnt];  //回溯 
    c[2][cnt]=!c[2][cnt];
    c[1][cnt-1]=!c[1][cnt-1];
    c[1][cnt+1]=!c[1][cnt+1];
    dfs(cnt+1,k);  //不按的情况 
} 

int main(){
    int t;
    cin>>t;
    while(t--){
        ans=inf;
        char x;
        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                cin>>x;
                c[i][j]=x-'0';
            }
        }
        dfs(1,0);
        if(ans<6)  cout<<ans<<endl;
        else  cout<<"-1"<<endl;
    }
    return 0;
}