AcWing 116. 飞行员兄弟

4*4=16
最终全部的状态的2的16次方=65536
暴力枚举所有方案，从方案里找到一个原始状态一摸一样的方案，对比一下求出最小步数；

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII; // PII.first, PII.second
const int N=5;

char g[N][N],backup[N][N];

// 二维映射的下标
// 将棋盘的每个每个位置标记为0，1，3，4，5 …
int get(int x,int y){
  return x*4+y;
}

// 改变当前方格元素的状态
void turn_one(int x,int y){
  if(g[x][y]=='+'){
    g[x][y]='-';
  }else{
    g[x][y]='+';
  }
}
// 改变这一整行和这一整列的所有元素
void turn_all(int x,int y){
  for(int i=0;i<4;i++){
    turn_one(x,i);  // 第x行第i个数
    turn_one(i,y);  // 第i行第y个数
  }
  turn_one(x,y);  // 上面x,y位置turn了两遍，抵消了，这里再turn一遍
}

int main(){
  //  输入矩阵状态
  for(int i=0;i<4;i++){
    cin>>g[i];  
  }
  vector<pair<int,int>> res; 
  for(int op=0;op <1 << 16;op++){ // 枚举2的16次方个方案
    vector<pair<int,int>> temp; // 存储暴力枚举的每一种方案
    memcpy(backup,g,sizeof(g));  // 备份
    
    // 1. 进行操作
    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_all(i,j);  // 改变这一整行和这一整列
        }
      }
    }
    
    // 2.判断所有灯泡是否全亮
    bool has_closed=false;  // 是否有灯泡是灭着的
    for(int i=0;i<4; i++){
      for(int j=0;j<4; j++){
        if(g[i][j]=='+'){
          has_closed = true;
        }
      }
    }
    if(has_closed==false){  // 说明所有灯泡都是亮着的
      if(res.empty()  || res.size() > temp.size()){  
        res=temp;
      }
    }
 memcpy(g,backup,sizeof(g));  // 还原
  }
  
  cout<<res.size() <<endl;
  for(auto op :res){
    cout<<op.first+1<<" "<<op.second+1<<endl; //下标加1
  }
  return 0;
}

原文地址：http://www.cnblogs.com/mengfengguang/p/16867200.html