算法分析

枚举第一行的所有按法，由下一行去更改上一行的状态，然后依次往下递推。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=10;
char g[N][N],bg[N][N];
int dx[]={-1,1,0,0,0},dy[]={0,0,-1,1,0};
void turn(int x,int y) //拉动(x,y) 
{
    for(int i=0;i<5;i++)
    {
        int a=x+dx[i],b=y+dy[i]; //相邻的点 
        if(a>=0&&a<5&&b>=0&&b<5)
        {
        	g[a][b]^=1; //改变 
		}
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int res=10;
        for(int i=0;i<5;i++)  //获取初始状态 
		{
			cin>>bg[i];
		}
        for(int op=0;op<32;op++) //枚举第一行每个操作 
        {
            memcpy(g,bg,sizeof g); //还原 
            int cnt=0;
            for(int j=0;j<5;j++) //枚举当前需要操作的行 
            {
            	 if(op>>j&1) //当前需要操作 
            	 {
            	 	 turn(0,j),cnt++;
				 } 
			}   
            for(int i=0;i<4;i++) //枚举每行 
                for(int j=0;j<5;j++)
                    if(g[i][j]=='0')
                        turn(i+1,j),cnt++;
            bool s=1;
            for(int j=0;j<5;j++) //判断最后一行 
                if(g[4][j]=='0')
                    s=0;
            if(s&&res>cnt) res=cnt; //符合答案 
        }
        if(res>6) res=-1; //无解 
        cout<<res<<endl;
    }
    return 0;
}