思路

逆向思维 我们从全是1考虑，6步以内能到达的状态hash记录一下。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,x) memset(a,x,sizeof(a))
#define SZ(x) ((int)(x).size())
#define lson rt<<1
#define rson rt<<1|1
#define pb push_back
#define fi first
#define se second
#define what_is(x) cerr<<#x<<" "<<x<<endl;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
template <typename T>
inline void _read(T& x){
    cin>>x;
}
void R(){}
template <typename T,typename... U>
void R(T&head,U&... tail){
    _read(head);
    R(tail...);
}

template <typename T>
inline void _write(const T& x){
    cout<<x<<' ';
}
void W(){cout<<endl;}
template <typename T,typename... U>
void W(const T&head,const U&... tail){
    _write(head);
    W(tail...);
}
template<typename T>
void debug(vector<T> V){
    for(auto x:V){
        cout<<x<<" ";
    }
    cout<<endl;
}
void go();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //cout<<fixed<<setprecision(8);
    go();
    return 0;
}
/*************************************/
unordered_map<int,int> mmp;
int now=0;
vi chosen;
int fun(int w){
    w--;
    int res=1<<w;
    int x=w/5;
    int y=w%5;
    if(x-1>=0){
        res+=1<<((x-1)*5+y);
    }
    if(x+1<=4){
        res+=1<<((x+1)*5+y);
    }
    if(y-1>=0){
        res+=1<<(x*5+(y-1));
    }
    if(y+1<=4){
        res+=1<<(x*5+(y+1));
    }
    return res;
}
void calc(int x){
    if(chosen.size()>6){
        return;
    }
    if(x>25){
        int step=chosen.size();
        int cur=(1<<25)-1;
        for(auto w:chosen){
            cur^=fun(w);
        }
        if(mmp.count(cur)==0){
            mmp[cur]=step;
        }else{
            mmp[cur]=min(mmp[cur],step);
        }
        return;
    }
    calc(x+1);
    chosen.push_back(x);
    calc(x+1);
    chosen.pop_back();
}
void init(){
    calc(1);
}
void go(){
    init();
    int T;
    R(T);
    rep(i,1,T){
        string str;
        now=0;
        rep(j,0,4){
            R(str);
            rep(k,0,4){
                int w=j*5+k;
                now+=str[k]=='1'?(1<<w):0;
            }
        }
        if(mmp.count(now)==0){
            cout<<-1<<endl;
        }else{
            cout<<mmp[now]<<endl;
        }
    }
}

2

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;

char str[MAXN][MAXN];

int mmp[MAXN][MAXN];
int num;

void change(int x, int y) {
    if (x < 0 || y < 0){
        return;
    }
    mmp[x][y] ^= 1;
}
void gao(int x, int y) {
    change(x, y);
    change(x + 1, y);
    change(x - 1, y);
    change(x, y + 1);
    change(x, y - 1);
}

void check() {
    for (int i = 1; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            if (!mmp[i - 1][j]) {
                if (num >= 6) {
                    num = 10;
                    return;
                }
                gao(i, j);
                num++;
            }
        }
    }
    for (int i = 0; i < 5; i++) {
        if (!mmp[4][i]){
            num = 10;
            return;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);// don't forget &

    while (n--) {
        for (int i = 0; i < 5; i++) {
            scanf("%s", str[i]);// no &
        }
        int ans = 10;
        for (int i = 0; i < 1 << 5; i++) {
            num = 0;
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    mmp[j][k] = str[j][k] - '0';
                }
            }

            for (int j = 0; j < 5; j++) {
                if ((i >> j) & 1){
                    num++;
                    gao(0, j);
                }
            }

            check();
            ans = min(ans, num);
        }
        printf("%d\n", ans == 10 ? -1 : ans);
    }

    return 0;
}