此题洛谷上亦有记载

实际上这个题还是dfs写法会多一点但是我不喜欢dfs

原题链接

其实只要确定第0行的状态，其余都是被锁死的 状态转移方程如下 设整行的最终状态为 $F_{i}$ 初始状态为 $A_{i}$ 开关按下的状态 为 $P_{i}$

原题目说了一个开关会波及到上下左右，所以状态转移方程为

$$F_i = A_i \oplus P_{i-1} \oplus P_i \oplus (P_i \ll 1) \oplus (P_i \gg 1) \oplus P_{i+1}$$​ ⊕为异或符号 题目的目标是让所有的灯全亮，因为是 5 列，所以全亮的状态就是二进制的 11111，也就是十进制的 31。我们要求 $F_i = 31$。 移项得$$P_{i+1} = 31 \oplus A_i \oplus P_{i-1} \oplus P_i \oplus (P_i \ll 1) \oplus (P_i \gg 1)$$

只要第一行的按法 $P_0$ 确定，后续的都能确定出来 代码如下

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[6],p[6];
string s;
int cnt(int x) {
    int r=0;
    while(x) {
        r+=x&1;
        x>>=1;
    }
    return r;
}
void solve() {
    for(int i=0;i<5;i++) {
        cin>>s;
        a[i]=0;
        for(int j=0;j<5;j++) {
            if(s[j]=='1') a[i]|=(1<<j);
        }
    }
    int an=10;
    for(int m=0;m<(1<<5);m++) {
        int c=0;
        p[0]=m;
        c+=cnt(p[0]);
        for(int i=0;i<4;i++) {
            int pr=(i==0)?0:p[i-1];
            p[i+1]=31^a[i]^pr^p[i]^((p[i]<<1)&31)^(p[i]>>1);
            c+=cnt(p[i+1]);
        }
        int f=a[4]^p[3]^p[4]^((p[4]<<1)&31)^(p[4]>>1);
        if(f==31) an=min(an,c);
    }
    if(an>6) cout<<-1<<'\n';
    else cout<<an<<'\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--) {
        solve();
    }
}