AcWing 95. 费解的开关

第一个难点：如何枚举第一行的操作（指数类型的枚举，可以使用第一题的指数型枚举）
这里使用二进制类型枚举
1 1 0 1 0 = 26
反过来任何一个整数0-65536 也可以用二进制表示

0-31 代表每一种方案
怎样看第i位是不是1； i>>k & 1

第二个难点： 如何写turn（x,y）函数

第三个问题： 时间复杂度

第四个问题：字符1和0互换

//  顺序无所谓
//  每个格子最多按一次
// 枚举第一行，第一行固定完，则第二行的操作是固定的
//  每一行开关的操作，完全被前一行的灯的亮灭状态所决定
// 如何枚举第一行的操作；

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=6;     // 5*5=25   ,2^25

char g[N][N];
char backup[N][N];
int dx[5]={-1,0,1,0,0};
int dy[5]={0,1,0,-1,0};
// 
void turn(int x,int y){
  for(int i=0;i<5;i++){ // 枚举5个位置
    int a=x+dx[i];
    int b=y+dy[i];
    if(a<0 || a>=5 || b<0 || b>=5 ){  // 判断边界
      continue ;
    }
    g[a][b]^=1;  // 把字符的0变为1，把字符的1变为0； （可以使用if或者使用位运算； 0的ascall码是48）
  }
}


int main(){
  int T;
  cin>>T;
  while(T--){
    for(int i=0;i<5;i++){
      cin>>g[i];    // 读入棋盘
    }
    int res=10;   //
    for(int op=0;op<32;op++){  // 枚举所有的方案
      memcpy(backup,g,sizeof(g));  // 复制，在备份的棋盘上面做操作
      int step=0;  // 走的步数
      for(int i=0;i<5;i++){  // 最大不超过5步
        if(op>>i&1){ // 判断当前位置要不要操作
          step++;
          turn(0,i);
        }
      }
      for(int i=0;i<4; i++){  //第1行决定第0行， 一直执行到倒数第一行
        for(int j=0;j<5;j++){ // 每一列
          if(g[i][j]=='0'){  // 当前是灭的
            step++;  // 步数加1
            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){ // 无解返回-1
      res=-1;
    }
    cout<<res<<endl;
  }
  
  
  return 0;
}