递推

暴力

C++ 代码

#include<bits/stdc++.h>

#define INF 0x3f3f3f3f
using namespace std;

const int N=6;
char g[N][N];
char tp[N][N];
int step;
int res;
bool success;

const int dx[5]={0,0,-1,1,0};
const int dy[5]={0,1,0,0,-1};
void turn(int x, int y){
    for(int i=0; i<5; i++){
        int ax=x+dx[i], ay=y+dy[i];
        if(ax<0||ay<0||ax>=5||ay>=5)continue;
        tp[ax][ay]^=1;
    }
}
int main(){
    int n; 
    scanf("%d",&n);

    while(n--){
        //输入 
        for(int i=0; i<5; i++){
            scanf("%s",&g[i]);
        }

        res=INF;
        //对于每种输入，第一行共有2^5种处理方法
        for(int pos1=0; pos1< 32; pos1++){
            //输入初始化，本次方法待处理数组
            step=0;
            memcpy(tp, g, sizeof(g));
            for(int i=0; i<pos1; i++){
                if(pos1>>i&1){//pos1的第i个位置为1，代表处理该位置 
                    step++;
                    turn(0, i);
                }
            } 

            //处理其他几行, 后一行根据前一行的状态判断是否在该位置处理 
            for(int i=0; i<4; i++){
                for(int j=0; j<5; j++){
                    if(tp[i][j]=='0'){
                        step++;
                        turn(i+1, j);
                    }
                }
            } 

            //判断
            success=true;
            for(int i=0; i<5; i++){
                if(tp[4][i]=='0'){
                    success=false;
                    break;
                }
            } 
            if(success){
                res=min(res, step);
            }
        } 
        if(res>6)cout << -1 << endl;
        else cout << res << endl;
    }
}