AcWing 95. 费解的开关
原题链接
中等
作者:
JosephWang
,
2021-01-31 10:53:14
,
所有人可见
,
阅读 4
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 6;
char g[N][N], backup[N][N];
int dx[5] = {-1, 0, 1,0,0}, dy[5] = {0,1,0,-1,0};
//偏移量
void turn(int x, int y){
for(int i = 0; i< 5; i++){
int a = x+dx[i], b = y+dy[i];
if(a<0 || a>=5 || b<0 || b>=5){
continue;//在边界外,直接忽略即可
}
g[a][b] ^=1;
}
}
int main(void){
int T;
cin>>T;
while(T--){
for(int i = 0; i<5; i++){
for(int j = 0; j<5; j++){
cin>>g[i][j];
}
}
//读入数据
int res = 10;
//假设一个比较大的数
for(int op = 0; op<32; op++){
//对第一行所有的操作进行枚举
//基本思想:对某一位的开或关的操作可以看成一个二进制数,比如00000就是全都不按,00001就是按最右边的一个
memcpy(backup, g, sizeof g);
//对g进行备份
int step = 0;
//初始步数是0
for(int i = 0; i<5; i++){
//操作的循环,目的是看op的哪几位是1,然后按那几位就可以了
if(op>>i&1){
//判断1的位置
step++;
//按了一下就把step增加1
turn(0,i);//按那个位置的灯,现在是对第一行操作,所以是0,i
}
}
//由于第一行确定了以后,后面的状况就完全确定了
for(int i = 0; i<4; i++){
for(int j = 0; j<5; j++){
if(g[i][j]=='0'){
step++;
turn(i+1, j);
}
}
}
bool dark = false;
//看最后一行是不是还有暗着的
for(int i = 0; i<5; i++){
if(g[4][i]=='0'){
dark = true;
break;
}
}
if(!dark){
res = min(res, step);
}
memcpy(g, backup, sizeof g);
//恢复现场
}
if(res>6)
{
res = -1;
}
cout<<res<<endl;
}
return 0;
}