Exercise 23, pilot brothers [binary enumeration / bit operation]

116. Pilot brother - AcWing Question bank

“ Pilot brother ” This game , Need the player to open a possession smoothly 16 A fridge with a handle .

It is known that each handle can be in one of the following two states ： Turn on or off .

Only when all the handles are open , The refrigerator will open .

The handle can be expressed as a 4×4 Matrix , You can change any position [i,j] Status of upper handle .

however , This will also make the i Xing He j The status of all the handles on the column also changes .

Please find out the minimum number of switching handles needed to open the refrigerator .

Input format
The input consists of four lines , Each line contains the initial state of four handles .

Symbol + Indicates that the handle is closed , And symbols - Indicates that the handle is open .

The initial state of at least one handle is off .

Output format
The first line outputs an integer N, Indicates the minimum number of switching handles required .

Next N Line description switching order , Output two integers per line , The row number and column number of the handle representing the switched state , The numbers are separated by spaces .

Be careful ： If there are many ways to open the refrigerator , Then according to the overall priority from top to bottom , Open from left to right .

Data range
1≤i,j≤4

sample input ：
-+--
----
----
-+--
sample output ：
6
1 1
1 3
1 4
4 1
4 3
4 4

#include<bits/stdc++.h>
using namespace std;
#define lint long long
#define pb push_back
int mp[20][20],add,mm[20][20];
void turn(int tp[20][20],int i,int j){ // change i That's ok j The switch state of the handle on the column 
    for(int k=1;k<=4;k++){
        tp[i][k]=!tp[i][k];
        tp[k][j]=!tp[k][j];
    }
    tp[i][j]=!tp[i][j];
}
int main(){
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++){
            char c;
            cin >> c;
            if(c=='+') mp[i][j]=0;
            else mp[i][j]=1;
        }

    for(int i=1;i<(1<<16);i++){ //1<<n Express 2 Of n Power , Here is the binary enumeration 
        int tp[20][20];
        memset(mm,0,sizeof(mm));
        for(int j=1;j<=4;j++)
            for(int k=1;k<=4;k++) tp[j][k]=mp[j][k];

        int x=1,y=0;
        add=0;
        for(int j=0;j<16;j++){
            y++;
            if(y==5){x++; y=1;}
            if(i>>j&1){ //i>>j&1 Judge binary i Of the j Whether a is 1
                mm[x][y]=1; // Record 
                add++;
                turn(tp,x,y);
            }
        }
        int flag=0;
        for(int j=1;j<=4;j++)
            for(int k=1;k<=4;k++)
                if(tp[j][k]==0) flag=1;
        if(flag==0){
            cout << add << endl;
            for(int j=1;j<=4;j++)
                for(int k=1;k<=4;k++) {
                    if(mm[j][k]==1) printf("%d %d\n",j,k);
                }
            return 0;
        }
    }
    return 0;
}