题目链接

https://ac.nowcoder.com/acm/problem/50920

解题思路

很重要的思想就是，
1.枚举对第0行的全部操作方案，从第1行开始的每一行，用当前行的开关去维护上一行灯的亮灭。
2.判断是否能使全部灯变亮，只需要去遍历最后一行，若不存在灭的灯，成立；因为前面的4行我们已经用其下一行都维护好了，都变成了亮的了。
3.当对第0行的操作固定时，是否能使全部灯变亮也已经确定了，且若可行，最少总转换开关的次数也就确定了。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;

int dir[5][2]={0,1,0,-1,1,0,-1,0,0,0};//包括自己的转换 
int ans,n,mp[10][10],tmp[10][10],step,f;
string str[10];

void turn(int i,int j)
{
    for(int t=0;t<5;t++)
    {
        int ii=i+dir[t][0],jj=j+dir[t][1];
        if(ii<0 || ii>=5 || jj<0 || jj>=5) continue;
        tmp[ii][jj]^=1;
    }
}

int main()
{
    cin>>n;
    while(n--)
    {
        for(int i=0;i<5;i++)
        cin>>str[i];
        for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
        mp[i][j]=str[i][j]-'0';//字符串转换成int数组 

        ans=INF;

        for(int s=0;s<(1<<5);s++)//枚举对第0行开关的操作，1代表摁下开关，0代表不摁开关（与灯亮灭无关） 
        {
            for(int i=0;i<5;i++)
            for(int j=0;j<5;j++)
            tmp[i][j]=mp[i][j];//把初始开关状态赋值到临时数组中，对临时数组操作 

            step=0;f=1;
            for(int i=0;i<5;i++)//对第0行的每一列遍历 
            if(s>>i&1)//如果当前列我们的操作是1，即摁下开关 
            {
                step++;//记录操作次数 
                turn(0,i);//对自己及周围四个（若存在4个）开关进行转换 
            }
            for(int i=1;i<5;i++)
            for(int j=0;j<5;j++)//遍历接下来的四行五列，每个开关只受它上面灯的影响 
            if(tmp[i-1][j]==0)//如果上面的灯是灭的，我们为了让全部灯变亮，就需要摁下当前开关，使得其上面的灯变亮 
            {
                step++;//记录操作次数 
                turn(i,j);//把当前灯转换 
            }

            for(int i=0;i<5;i++)//遍历第4行，即最后一行灯 
            if(tmp[4][i]==0)//如果存在灯是灭的，说明最初我们对第0行灯的操作不合法，无法使全部灯点亮 
            {
                f=0;
                break;
            }
            if(f) ans=min(ans,step);//如果操作方案合法，统计最小操作数 
        }
        if(ans>6) cout<<-1<<endl;//如果最小操作数都大于6，输出-1 
        else cout<<ans<<endl;
    }
}