思路
1 按法与顺序无关
2 每个格子最多按一次(最小步数)
3 每一行开关的操作 完全被前一行灯的亮灭状态所决定
坐标的通常表示形式
—————————y
|
|
|
|
x
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=6;
int n;
char state[N][N],backup[N][N];
int dx[N]={-1,0,1,0,0};
int dy[N]={0,1,0,-1,0};
void turn(int x,int y){
for(int i=0;i<5;i++){
int a=x+dx[i];//简化表示 偏移量
int b=y+dy[i];
if(a<0||a>=5||b<0||b>=5) continue;//如果在边界 直接跳过到下一个数
state[a][b]^=1;//把0变成1 把1变成0
}
}
int main(){
cin>>n;
while(n--){//执行n次操作
for(int i=0;i<5;i++) cin>>state[i];
int res=7;
for(int op=0;op<32;op++){
memcpy(backup,state,sizeof state);
int step=0;
//枚举第一行
for(int j=0;j<5;j++)
if(op>>j&1) {//位运算 看op的j位是不是1
step++;
turn(0,j);
}
//2-4行
for(int x=0;x<4;x++)
for(int y=0;y<5;y++)
if(state[x][y]=='0') {//是字符'0' 不能写成整数0
step++;
turn(x+1,y);
}
//最后一行 看会不会有灯灭不了 直接去掉
bool dark=false;
for(int y=0;y<5;y++){
if(state[4][y]=='0') {//又把==写成=了 调了快一个小时才发现!!!
dark=true;
break;
}
}
if(!dark) res=min(res,step); //res表示32种按法中的最小值
memcpy(state,backup,sizeof state); //backup的作用是将每次的state复原(turn中改变了) 而不是代替state变化
}
if(res>6) res=-1;
cout<<res<<endl;
}
return 0;
}