费解的开关题解

用深搜做该题时，对每一个点都遍历一遍会超时
所以应该对其优化
先来看例子
1 0 1 1 1
0 1 1 0 1
1 0 1 1 1
1 0 0 0 0
1 1 0 1 1
先看第一行，若我们想修改第一行的值，只需要修改位于它下面的值
如
1 1 1 1 1
1 0 0 0 1
1 1 1 1 1
1 0 0 0 0
1 1 0 1 1
此时第一行已全为1，然后再进行第二行
1 1 1 1 1
1 1 1 1 1
0 1 0 1 0
1 1 1 1 0
1 1 0 1 1
然后再对第三行进行
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 1 0 1 1
0 1 1 1 0
再进行第四行
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 0 0 0
可见第五行已经不能再改变了，这样显然不能得到全为1的二维数组，说明当第一行元素是这样的情况就不能成立
所以我们可以对第一行进行改变，只需要枚举第一行五个开关即可，然后按刚才的方法看是否能够全部变为1.

#include<bits/stdc++.h>
using namespace std;
const int Inf=0x3f3f3f;
const int MAXN=10;
int map1[MAXN][MAXN];
int map2[MAXN][MAXN];
int check;
int checking(int t)
{
    int sum=t;
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            map2[i][j]=map1[i][j];
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=5;j++)
        {
            if(!map2[i][j])
            {
                sum++;
                map2[i][j]=!map2[i][j];
                map2[i+1][j]=!map2[i+1][j];
                map2[i+1][j-1]=!map2[i+1][j-1];
                map2[i+1][j+1]=!map2[i+1][j+1];
                map2[i+2][j]=!map2[i+2][j];

            }
        }

    }
    for(int i=1;i<=5;i++)
        if(!map2[5][i])
            return Inf;
    return sum;
}
void dfs(int x,int y)//x为第一行元素的下标，y为第一行打开开关的次数 
{
    if(x>5)
    {
        check=min(check,checking(y));
        return;
    }
    map1[1][x]=!map1[1][x];
    map1[1][x-1]=!map1[1][x-1];
    map1[1][x+1]=!map1[1][x+1];
    map1[2][x]=!map1[2][x];
    dfs(x+1,y+1);
    map1[1][x]=!map1[1][x];
    map1[1][x-1]=!map1[1][x-1];
    map1[1][x+1]=!map1[1][x+1];
    map1[2][x]=!map1[2][x];
    dfs(x+1,y);

}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {

        for(int i=1;i<=5;i++)
        {
            for(int j=1;j<=5;j++)
            {
                scanf("%1d",&map1[i][j]);
            }
        }
        check=Inf;
        dfs(1,0);
        if(check<7)
            printf("%d\n",check);
        else
            printf("-1\n");
    }
    return 0;
}