二进制写法
#include<bits/stdc++.h>
using namespace std;
int g[6][6];//储存每个灯的状态
int backup[6][6];
int T;//T组数据
void turn(int x,int y)
{
int dx[5]={0,0,-1,1,0};
int dy[5]={1,-1,0,0,0};
for(int i=0;i<5;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<1||a>5||b<1||b>5) continue;
g[a][b]=!g[a][b];
}
}
int main()
{
cin>>T;
while(T--)
{
for(int i=1;i<=5;i++)
for(int j=1;j<=5;j++)
scanf("%d",&g[i][j]);
int res=10;//记录每次方案中所用操作次数最少的
for(int op=0;op<=31;op++)//第一行五个元素都有按开关和不按开关两种选择,共2^5种情况
{
int number=0;//储存操作次数
memcpy(backup,g,sizeof g);//备份
for(int i=0;i<=4;i++)//依次看右移0,1,2,3,4位后末位是1还是0,分别对应着第一行1,2,3,4,5号灯泡是否按下开关
{
if(op>>i&1)//op的右移i位如果是1,则第一行第i+1号灯泡按下开关
{
turn(1,i+1);
number++;
}
}
for(int i=1;i<=4;i++)//从第2行开始,依次根据上一行灯泡状态开关此行开关,使上一行灯泡全亮
for(int j=1;j<=5;j++)
{
if(g[i][j]==0)
{
turn(i+1,j);
number++;
}
}
int flag=0;
for(int i=1;i<=5;i++)//枚举第五行所有灯泡,看是否全亮
{
if(g[5][i]==0)
{
flag=1;//存在不亮的灯泡
break;
}
}
if(!flag)//如果全亮,更新最少操作次数
res=min(res,number);
//cout<<flag<<endl;
memcpy(g,backup,sizeof g);
}
//cout<<res<<endl;
if(res<=6)
cout<<res<<endl;
else
cout<<-1<<endl;
}
}
dfs写法
#include<bits/stdc++.h>
using namespace std;
int g[6][6];//储存每个灯的状态
int backup[6][6];
int T;//T组数据
int res;//记录每次方案中所用操作次数最少的
int st[6];//记录第一行五个灯泡按与不按开关的选择,0还没选择,1表示按,2表示不按
void turn(int x,int y)
{
int dx[5]={0,0,-1,1,0};
int dy[5]={1,-1,0,0,0};
for(int i=0;i<5;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<1||a>5||b<1||b>5) continue;
g[a][b]=!g[a][b];
}
}
void dfs(int u)
{
if(u>5)//五个灯泡按和不按开关的情况都确定后
{
int number=0;//储存操作次数
memcpy(backup,g,sizeof g);//备份
for(int i=1;i<=5;i++)//依次看1,2,3,4,5号灯泡是否按下开关
{
if(st[i]==1)//第一行第i号灯泡按下开关
{
turn(1,i);
number++;
}
}
for(int i=1;i<=4;i++)//从第2行开始,依次根据上一行灯泡状态开关此行开关,使上一行灯泡全亮
for(int j=1;j<=5;j++)
{
if(g[i][j]==0)
{
turn(i+1,j);
number++;
}
}
int flag=0;
for(int i=1;i<=5;i++)//枚举第五行所有灯泡,看是否全亮
{
if(g[5][i]==0)
{
flag=1;//存在不亮的灯泡
break;
}
}
if(!flag)//如果全亮,更新最少操作次数
res=min(res,number);
memcpy(g,backup,sizeof g);
return;
}
for(int i=1;i<=2;i++)
{
st[u]=i;
dfs(u+1);
st[u]=0;
}
}
int main()
{
cin>>T;
while(T--)
{
for(int i=1;i<=5;i++)
for(int j=1;j<=5;j++)
scanf("%1d",&g[i][j]);
res=10;
dfs(1);
if(res<=6)
cout<<res<<endl;
else
cout<<-1<<endl;
}
}