题目链接https://www.acwing.com/problem/content/description/97/

题目要求把所有的0都按成 1 如果按不了则输出 -1 找最小的改变次数，可以用广搜寻找最短的路径，也可以用递推，首先每个开关只会被按一次，而且如果固定了第一行则本题只有唯一的一种解法，因为第一行被固定则第二行的点击情况也是被固定的（假如第一行某一位为0则要通过改变第二行才能把第一行都变为1）同样道理后面第3、4、…n都是被固定的所以只有一种解

因此我们只需要枚举第一行的所有改变情况就可以知道每一种情况的所有解进而更新ans得到最小值

最后一行因为没办法改变（因为没有下一行了）所以只能全为1不然一定没有解所以开一个bool来判断是否更新ans

#include<iostream>
#include<cstring>
using namespace std;

const int q = 10;
const int INF = 10000000;
char map[q][q];
int cnt = 0;

void turn(int x,int y)
{
    //枚举五个方向
    int dx[5] = {0,0,0,-1,1};
    int dy[5] = {0,1,-1,0,0};
    for(int i = 0;i<5;i++)
    {
        int a = x+dx[i];
        int b = y+dy[i];
        if(a>=0&&a<5&&b>=0&&b<5)
            map[a][b] ^= 1;//取反要用1 而不是‘1’
    }
}
int work()
{

    int ans = INF;
    for(int i = 0;i< 1<<5;i++)
    {
      
        char backup[q][q];
        int cnt = 0;//初始化为0 按的次数
        memcpy(backup,map,sizeof map);//拷贝一份存在backup中然后操作map每次枚举不会改变原数组
        for(int j = 0;j<5;j++)
        {
            if(i >> j & 1)//遇到1就按一次，这里的1不是开关状态的一，而是对不对该开关进行操作若1则按，0不按
            {
                cnt++;
                turn(0,j);
            }
        }
        for(int k = 0;k<4;k++)//枚举0 到 3可以递推出 1 到 4的填法
            for(int j = 0;j<5;j++)
                {
                    if(map[k][j] == '0')
                    {
                        cnt++;
                        turn(k+1,j);
                    }
                }
        bool is_successful = true;
        for(int j = 0;j<5;j++)
            if(map[4][j] == '0')
            {
                is_successful = false;
                break;
            }
         if(is_successful) ans = min(ans,cnt);//选最小值
         memcpy(map,backup,sizeof map);//一定要拷贝回来，不然数组在枚举时已经被改变了
    }
    if(ans > 6)return -1;
    else return ans;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        for(int i = 0;i<5;i++)
            cin>>map[i];
            cout<<work()<<endl;
    }
}