藍橋杯每日一題（二進制枚舉）

飛行員兄弟

知識點：二進制枚舉 遞推

“飛行員兄弟”這個遊戲，需要玩家順利的打開一個擁有 16 個把手的冰箱。

已知每個把手可以處于以下兩種狀态之一：打開或關閉。

隻有當所有把手都打開時，冰箱才會打開。

把手可以表示為一個 4×4 的矩陣，您可以改變任何一個位置 [ i , j ] [i,j] [i,j] 上把手的狀态。

但是，這也會使得第 i 行和第 j 列上的所有把手的狀态也随着改變。

請你求出打開冰箱所需的切換把手的次數最小值是多少。

輸入格式

輸入一共包含四行，每行包含四個把手的初始狀态。

符号

+

表示把手處于閉合狀态，而符号

-

表示把手處于打開狀态。

至少一個搖桿的初始狀态是關閉的。

輸出格式

第一行輸出一個整數 N，表示所需的最小切換把手次數。

接下來 N 行描述切換順序，每行輸出兩個整數，代表被切換狀态的把手的行号和列号，數字之間用空格隔開。

注意：如果存在多種打開冰箱的方式，則按照優先級整體從上到下，同行從左到右打開。

資料範圍

1≤i,j≤4

輸入樣例：

-+--
----
----
-+--
           

輸出樣例：

6
1 1
1 3
1 4
4 1
4 3
4 4
           

//注意到資料範圍很小，每一個開關隻有兩個狀态，故可以使用二進制枚舉，一共十六位，如果該位為1時則對開關操作
//最後判斷是否全為"-",每操作一次注意拷貝原數組，最後再還原
//16個位置映射到0~15，由坐标映射 --> 4x+y;
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define over1(i,s,t) for(int i=s;i<=t;i++)
#define over2(i,s,t) for(int i=s;i<t;i++)
typedef pair<int,int> PII;
char g[5][5],backup[5][5];
int get(int x,int y){//每一個位置映射到0~15
    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){
    over2(i,0,4){
        turn_one(x,i);
        turn_one(i,y);
    }
    turn_one(x,y);
}
int main(){
    over1(i,0,3) cin>>g[i];
    over2(op,0,1<<16){
        memcpy(backup,g,sizeof g);
        vector<PII>v;
        over2(i,0,4){
            over2(j,0,4)
            if(op>>get(i,j)&1) {
                v.push_back({i,j});
                turn_all(i,j);
        }
    }
    bool flag=false;
    over2(i,0,4){
        over2(j,0,4){
            if(g[i][j]=='+'){flag=true;break;}
        }
    }
    if(!flag){
        cout<<v.size()<<endl;
        for(auto t:v) cout<<t.first+1<<" "<<t.second+1<<endl;
    }
    memcpy(g,backup,sizeof g);
}
     return 0;
}