题目
讲解
先将两个比较重要的性质：
- 对于一个按钮，不可能按两次，按两次就等于不按。
- 按按钮的顺序不会影响最终结果。（也就是无序）
至于为什么，可以结合位运算来思考，在此不多讲了。
仍然分成做法1和做法2。
做法1（我的做法）
没错，我的做法就是暴力，传统艺能。
为了节省空间，我把(1)设为灯是暗的，(0)是亮的。（实际上并没有节省）
然后就变成了我们要让图全部变成(0)了，但是我们发现这个操作是可逆的，如果(X)能花(5)步变成(Y)，那(Y)也能花(5)步变成(X)，重点是数据范围是(5*5)的，而(2^{25}-1=33554431)，那么我们就可以直接用一个(int)来反映整个图的开关情况了，然后我们预处理出(0)状态到(X)状态所需要的步数就行了，对于超过(6)步的就不理他了。
当然我还有一个性质不知道怎么证的，只是觉得他是对的，但是不会证，但我也用了因为我找不出反例。（其实不用改成min就行了）
对于每个按钮，不可能通过按其他的按钮来实现这个按钮的功能，这意味着(0)到每个图所需要按的按钮是唯一的。
时间复杂度：(O(C_{25}^{6}+n))
#include<cstdio>
#include<cstring>
#define N 41000000
using namespace std;
int a[N];
inline int close(int x/*状态*/,int k/*位置*/)
{
x^=(1<<(k-1));
if(k%5!=0)x^=(1<<k);
if(k%5!=1)x^=(1<<(k-2));
if(k>5)x^=(1<<(k-6));
if(k<=20)x^=(1<<(k+4));
return x;
}
void dfs(int k/*表示状态*/,int t/*表示这次是第几次开灯了*/,int x/*这是决定在哪里开灯的*/)
{
a[k]=t;//记录状态，这里就用到了那个神奇的性质了
if(t==6 || x>25)return ;//以后都不可能开灯了
dfs(close(k,x),t+1,x+1);//开灯
dfs(k,t,x+1);//不在这里开灯
}
int main()
{
int T;scanf("%d",&T);
dfs(0,0,1);
while(T--)
{
char st[10];
int x=0;
for(int i=1;i<=5;i++)
{
scanf("%s",st+1);
for(int j=1;j<=5;j++)
{
if(st[j]=='0')x^=(1<<((i-1)*5+j-1));
}
}
if(x==0)printf("0
");
else if(a[x]==0)printf("-1
");
else printf("%d
",a[x]);
}
return 0;
}
做法2
奆佬就是奆佬，惹不起惹不起。
果然，不出所料。
这个做法要从我们看这个开关的角度来看了，开关是一个“十”字的构造，题目中是说点中间影响四周，但是我们可以看成我们点了上面的开关，影响了下面四个开关，这样子看的话，我们点开关的时候就可以一层层向下推进了。
但是这样存在两个问题。
-
不是最少的点击次数，例如：
000
101
111
如果按照这种方法按的次数是远大于(3)的，而且题目中都说了我们按了中间影响了四周，所以我们必须要考虑第一行是中间的情况，对于这种情况，奆佬选择了直接暴力枚举操作序列，比如我枚举到了(00110)，说明我会按3、4号开关，但是这会花费(2^5)的代价足足32啊，四舍五入就是一个亿啊，然后再按这个做法做，就解决了这种情况。 -
不能完美的把图变成(0)。
如：
000
101
111
我们用我们的方法处理第一行：
111
111
000
第二行不用处理了，但到了第(3)行，我们就不能用这个方法了，因为我们其实只是把按按钮换了个角度看，实际位置并没变，如果我们按那个方法接着做，那么按开关的实际位置就是在第(4)行了。
而且这也恰巧为按钮方案唯一这个提供了有力的证据，第一个问题是不是最少的点击次数，但是根据这个性质理论上来讲只存在一个点击次数啊，所以这个问题就说明了，这种方式构造出的方案不仅点击次数多，而且还是错误。
至于解决的方法，就是不让最后一行参与到这个方法中，同时在做完之后看看图是否满足要求就行了。（其实只用检查最后一行）
时间复杂度：(O(2^5*5^2*n))
代码采用https://www.acwing.com/solution/content/804/：
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,k,a[7][7],ans1=1e6,b[7][7];//7,7是因为怕在最后一排溢出
int main()
{
int n;
cin>>n;
while(n--)
{
getchar();
for (i=1;i<=5;i++)
{
for (j=1;j<=5;j++)
{
char ch=getchar();
b[i][j]=ch-'0';
}
getchar();
}
for (i=0;i<=(1<<5);i++)//模拟第一行的操作序列
{
for (j=1;j<=5;j++)
{
for (k=1;k<=5;k++)
a[j][k]=b[j][k];
}
int ans=0;
for (j=1;j<=5;j++)
if (i>>(j-1) & 1)
{
ans++;
a[1][j-1]^=1;
a[1][j+1]^=1;
a[1][j]^=1;
a[2][j]^=1;
}
for (j=1;j<=4;j++)//切记是1~4，而不是2~5，因为我们是控制i+1行，而不是控制第i行
for (k=5;k>=1;k--)
if (!a[j][k])
{
ans++;
a[j][k]^=1;//上面
a[j+2][k]^=1;//下面
a[j+1][k]^=1;//本身
a[j+1][k+1]^=1;//右面
a[j+1][k-1]^=1;//左面
}
//cout<<ans<<endl;
bool ok=true;
for (j=1;j<=5;j++)
for (k=1;k<=5;k++)
if (!a[j][k])
ok=false;
if (ok)
ans1=min(ans1,ans);//,cout<<ans<<endl;
}
if (ans1>6)
cout<<-1;
else
cout<<ans1;
ans1=1e7;
puts("");
}
return 0;
}