acwing116. 飞行员兄弟

题目

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个 4×4 的矩阵，您可以改变任何一个位置 [i,j] 上把手的状态。

但是，这也会使得第 i 行和第 j 列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

题解

• 位运算
  将16个开关看成2进制的16位数，如果(i,j)处于闭合状态，那么累加起来得到一个值。然后枚举1-1<<16的数开始变换，最后变成0说明所有开关都打开了。

#include<iostream>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
vector<PII> path;
int change[4][4];
int get(int x,int y){
    return x*4+y;
}
int main(){
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            for(int k=0;k<4;k++)change[i][j]+=(1<<get(i,k))+(1<<get(k,j));
            change[i][j]-=1<<get(i,j);
        }
    }
    int state=0;
    for(int i=0;i<4;i++){
        string line;
        cin>>line;
        for(int j=0;j<4;j++){
            if(line[j]=='+')state+=(1<<get(i,j));
        }
    }
    int ans=10; 
    vector<PII>path;
    for(int i=0;i<1<<16;i++){
        int now=state;
        vector<PII>temp;
        for(int j=0;j<16;j++){
            if(i>>j&1){
                int x=j/4,y=j%4;
                now^=change[x][y];
                temp.push_back({x,y});
            }
        }
        if(!now&&(path.empty()||path.size()>temp.size()))path=temp;
    }
    cout<<path.size()<<endl;
    for(int i=0;i<path.size();i++)
        cout<<path[i].first+1<<" "<<path[i].second+1<<endl;
    return 0;
}

• 数组写法

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
vector<PII> path;
char g[4][4],backup[4][4];
void turnone(int x,int y){
    if(g[x][y]=='+')g[x][y]='-';
    else g[x][y]='+';
}
void turnall(int x,int y){
    for(int i=0;i<4;i++){
           turnone(x,i);
           turnone(i,y);
    }
    turnone(x,y);
}
int get(int x,int y){
    return x*4+y;
}
int main(){
    for(int i=0;i<4;i++){
        cin>>g[i];
    }
    for(int i=0;i<1<<16;i++){
        vector<PII>temp;
        memcpy(backup,g,sizeof g);
        for(int j=0;j<4;j++){
            for(int k=0;k<4;k++){
                if(i>>get(j,k)&1){
                    turnall(j,k);
                    temp.push_back({j,k});
                }
            }
        }
        bool all_closed=false;
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
                if(g[j][k]=='+')all_closed= true;
        if(all_closed==false){
            if(path.empty()||path.size()>temp.size())path=temp;
        }
        memcpy(g,backup,sizeof g);
    }
    cout<<path.size()<<endl;
    for(int i=0;i<path.size();i++)
        cout<<path[i].first+1<<" "<<path[i].second+1<<endl;
    return 0;
}