ACAG 0x02-4 费解的开关
对于这道题，我们不难发现如下性质：
- 每个位置之多被点击一次；
- 点击的先后顺序不影响结果；
- 若确定了第$1$行，则接下来可能的点击方案就只有$1$种。具体原因是：当第$i$行某一位为$0$时，此时前$i$行均已确定，所以只能点击第$i+1$行该位置上的数，才能使第$i$行的这一位变成$1$。
于是，我们只需要考虑第一行的点击方法。不难枚举得，共$32$种。我们可以用$0$~$31$的二进制表示点击方法。
然后，对于每种方法，我们可以递推出接下来$2$~$5$行的点击方法，最后进行检查。如果矩阵全变为$1$，则说明该方案合法。并更新答案。
此外，在检查的时候，只需要检查最后$1$行即可。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n,ans,tmp;
int a[7][7],b[7][7];
char s[7];
void Read() {
for(int i=1;i<=5;i++) {
cin>>(s+1);
for(int j=1;j<=5;j++) {
a[i][j]=s[j]-'0';
}
}
ans=INF;
return;
}
void Init() {
for(int i=1;i<=5;i++) {
for(int j=1;j<=5;j++) {
b[i][j]=a[i][j];
}
}
tmp=0;
return;
}
void Change(int x,int y) {
b[x][y]==1?b[x][y]=0:b[x][y]=1;
b[x][y-1]==1?b[x][y-1]=0:b[x][y-1]=1;
b[x][y+1]==1?b[x][y+1]=0:b[x][y+1]=1;
b[x-1][y]==1?b[x-1][y]=0:b[x-1][y]=1;
b[x+1][y]==1?b[x+1][y]=0:b[x+1][y]=1;
tmp++;
return;
}
bool Check() {
if(tmp>6) {
return false;
}
for(int i=1;i<=5;i++) {
if(b[5][i]==0) {
return false;
}
}
return true;
}
void DFS(int x) {
if(x==6) {
if(Check()) {
ans=min(ans,tmp);
}
return;
}
for(int i=1;i<=5;i++) {
if(b[x-1][i]==0) {
Change(x,i);
}
}
DFS(x+1);
}
void Solve() {
for(int i=0;i<=31;i++) {
Init();
for(int j=0;j<=4;j++) {
int x=(i>>j)&1;
if(x) {
Change(1,j+1);
}
}
DFS(2);
}
printf("%d\n",ans==INF?-1:ans);
return;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) {
Read();
Solve();
}
return 0;
}