C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 376K, 提交时间: 2019-12-07 20:43:21

#include<cstdio>
using namespace std;
int ans,T;

inline int flip(int &x,int i) {
	x^=(1<<i);
	if (i%5!=4) x^=(1<<(i+1));
	if (i%5) x^=(1<<(i-1));
	if (i>4) x^=(1<<(i-5));
	if (i<20) x^=(1<<(i+5));
}

void check(int x,int p){
	int cnt=0;
	for (int i=0;i<5;i++)
	 if ((p>>i)&1)
	  flip(x,i),++cnt;
	
	for (int i=0;i<4;i++)
	 for (int j=0;j<5;j++)
	  if (!((x>>(i*5+j))&1)){
	  	flip(x,i*5+j+5);
	  	if (++cnt>=ans) 
		  return;
	  }
	  
	if ((x>>20)==31) ans=cnt;
}

int main(){
	//freopen("a.in","r",stdin);
	scanf("%d",&T);
	
	while(T--){
		int y=0;
		ans=7;
		for (int i=0,x; i<5; i++)
			for (int j=0; j<5; j++)
				scanf("%1d",&x),y=(y<<1)+x;
	
		for (int state=0;state<32;state++) check(y,state);
		
		ans==7 ? puts("-1"):printf("%d\n",ans);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 825ms, 内存消耗: 12624K, 提交时间: 2020-02-25 23:34:54

#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
queue<int> q;
map<int,int> ans;
int T;
inline int flip(int x,int i)
{
	x^=(1<<i);
	if(i%5!=4) x^=(1<<(i+1));
	if(i%5) x^=(1<<(i-1));
	if(i>4) x^=(1<<(i-5));
	if(i<20) x^=(1<<(i+5));
	return x; 
}
int main()
{
	scanf("%d",&T);
	q.push((1<<25)-1),ans[(1<<25)-1]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		if(ans[x]==7) break;
		for(int i=0,y;i<25;i++)
		if(ans[y=flip(x,i)]==0)
		q.push(y),ans[y]=ans[x]+1;
	}
	while(T--)
	{
		int y=0;
		for(int i=0,x;i<5;i++)
		for(int j=0;j<5;j++)
		scanf("%1d",&x),y+=x<<(i*5+j);
		printf("%d\n",ans[y]?ans[y]-1:-1);
	}
}