题解
题目解析
这道题目刚开始看没有一点头绪,因为所有的开关都是可以随便按的,没有顺序按的,这就导致了极大的随机性,其实可以暴力枚举,但是每个格子都有两种状态,有25个格子,因此有2^25,估算一下2^25 > 10^8,因此不能进行暴力枚举
听了课程以后,发现可以通过按动第一行开关,间接推出第二行,第三行,第四行,第五行的按动情况。
思路
1、随机按第一行。
2、第二行 至 第五行的开关不能随便按,需要上一行的同一列的开关时灭的才按。
这种按动方法可以保证,上一行的灯全部都是亮的。
3、如此循环直到最后一行按动完毕,当最后一行按动完毕也就保证了除了最后一行,其他行全部都是亮的。
因此可以枚举最后一行的灯的亮灭情况,来判断第一行的按动是否正确,以及这种状态是否有解。
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 6;
char lan[N][N],ter[N][N];//因为存的是字符串,最后以'\0'结尾,要多空出一个位置
int dx[] = {-1 ,1 ,0 ,0 ,0 } , dy[] = {0 ,0 ,-1 ,1 ,0};//上、下、左、右、中
//改变开关
void turn(int x,int y)
{
int a = 0,b = 0;//a表示新的行,b表示新的列
for(int i = 0 ; i<5 ; i++)//5个方位进行改变
{
a = x + dx[i] ,b = y + dy[i] ;
if( a>= 0 && a<= 4 && b>=0 && b<=4)
{
ter[a][b] ^= 1;
}
}
}
int main()
{
int n;
cin>>n;//n个状态
for(int T = 0 ; T<n ; T++)
{
//输入一种状态
for(int i = 0 ; i<5 ; i++) cin>>lan[i];//输入5行字符串
int ans = 100;//答案步数,先赋值为比较大的数字,方便更新
int res = 0;//最多6步,否则不成功,res 表示步数
//枚举第一行的所有开关情况
for(int op = 0 ; op<= 31 ; op++) //5个字符一共有2^5种操作00000 - 11111,32种操作
{
res = 0;//更新为0步
memcpy(ter , lan , sizeof lan);//拷贝一份到ter里面,进行操作ter
for(int i = 0 ; i<5 ; i++)
{
if(op >> i & 1)//op>>i 表示op右移i位, &1 表示最低位和1相与,1 & 1 = 1, 0 & 1 = 0
{
turn(0 , i);//op最低位是1,改变一次状态
res++;//这里最多执行5步
}
}
//第一行状态已经确定,其他行照样推即可,最后一行也要改变,用于判断
for(int i = 1 ; i<5 ; i++) //2 - 4行
{
for(int j = 0 ; j<5 ; j++)
{
if(ter[i - 1][j] == '0')//当上面的灯灭了,下面的灯就要改变一次
{
turn(i , j);
res++;
if(res > 6) break;
}
}
if(res > 6) break;
}
if(res > 6) continue;
//判断最后一行
for(int i = 0 ; i<5 ; i++)
{
if(ter[4][i] == '0')
{
res = -1;
break;
}
}
if(res != -1)//说明这种情况符合,需要更新
{
//更新步数
ans = min(ans , res);
}
}
if(ans <= 6) cout<<ans<<endl;
else cout<<-1<<endl;
}
return 0;
}