116. 飞行员兄弟刷题笔记

/*
二进制枚举
两个状态
1.将0-2^16-1
的二进制表示映射成
所有的方案
2.逐步检查该二进制数每一位
对该位与上1 如果成立则该改变改行该列的状态
写一个 get函数
将i j转化为当前二进制的位数

3. 检查所有的把手状态
是否都打开
*/

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N=5;
typedef pair<int ,int > PII;
char g[N][N],backup[N][N];
int get(int i,int j){
   //get函数将二维位置转为二进制的位数第几位
   return i*4+j;
}
void turn_one(int i,int j){
   if(g[i][j]=='+'){
       g[i][j]='-';
   }else{
       g[i][j]='+';
   }
   //换单个把手的状态
}
void turn_(int x,int y){
   ///模拟可知
   //每次之会切换七个把手的状态
   for(int i=0;i<4;i++){
       turn_one(x,i);//行的切换
       turn_one(i,y); //列的切换
   }
   turn_one(x,y);//自身切换
}

int main(){
   for(int i=0;i<4;i++){
       cin>>g[i];
   }
   vector<PII> res;
   for(int op=0;op<1<<16;op++){
       //op映射方案
       vector<PII> temp;//记录操作
       memcpy(backup,g,sizeof g);//备份便于修改后的复原
       for(int i=0;i<4;i++){
           for(int j=0;j<4;j++){
               if(op>>get(i,j)&1){
                   temp.push_back({i,j}); //记录操作
                   turn_(i,j);//切换状态
               }
           }
       }
       bool haveclose =false;
       //检查操作完后是否满足条件

       for(int i=0;i<4;i++){
           for(int j=0;j<4;j++){
               if(g[i][j]=='+'){
                   haveclose =true;
               }
           }
       }
       if(haveclose==false)
       {
           if(res.empty() ||res.size() >temp.size() )
           {
               res=temp;
           }
       }

       memcpy(g,backup,sizeof g);
   }
   cout<<res.size() <<endl;
   for(int i=0;i<res.size() ;i++){
       cout<<res[i].first+1<<' '<<res[i].second+1<<endl;
       //答案从开始数所以加 1
   }
   return 0;
}