题解：P10456 The Pilots Brothers' refrigerator

jinfanhao · 2024-12-27 22:37:54 · 题解

这道题是道很好的二进制枚举练习题。\ 我们可以发现你一个手柄，无论操作只要重复了，就抵消掉了。\ 这样我们可以用一个二进制数 i 来表示操作方案，如果这一位是 1，那么就是可以操作，否则就是不操作。

#include<bits/stdc++.h>
using namespace std;
char ch[5][5];
int op[5][5],f,minx=INT_MAX,ans;
signed main(){
    for(int i=1; i<=4; ++i){
        for(int j=1; j<=4; ++j){
            cin >> ch[i][j];
            if(ch[i][j]=='-')op[i][j]=1;
            if(ch[i][j]=='+')op[i][j]=0;
        }
    }
    for(int i=0; i<(1<<16); ++i){
        int sum=0;
        for(int j=1; j<=16; ++j){
            if(i&(1<<(j-1))){
                ++sum;
                int x=(j-1)/4+1,y=j%4;
                if(!y)y=4;
                for(int k=1; k<=4; ++k){
                    op[x][k]^=1;
                    op[k][y]^=1;
                }
                op[x][y]^=1;
            }
        }
        bool ok=true;
        for(int j=1; j<=4; ++j){
            for(int k=1; k<=4; ++k){
                if(!op[j][k]){
                    ok=false;
                    break;
                }
            }
            if(!ok)break;
        }
        if(ok && sum<minx){
            minx=sum;
            ans=i;
        }
        for(int j=1; j<=16; ++j){
            if(i&(1<<(j-1))){
                ++sum;
                int x=(j-1)/4+1,y=j%4;
                if(!y)y=4;
                for(int k=1; k<=4; ++k){
                    op[x][k]^=1;
                    op[k][y]^=1;
                }
                op[x][y]^=1;
            }
        }
    }
    printf("%d",minx);
    for(int i=1; i<=16; ++i){
        if(ans&(1<<(i-1))){
            int x=(i-1)/4+1,y=i%4;
            if(!y)y=4;
            printf("\n%d %d",x,y);
        }
    }
    return 0;
}