1 条题解

  • 1
    @ 2021-8-7 18:41:44

    C++ :

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    typedef pair<int,int> PII;
    int change[4][4];
    int get(int x,int y){//二维转一维
        return x * 4 + y;
    }
    int main(){
        int st = 0;
        for(int i = 0;i < 4;i++){
            string line;
            cin>>line;
            for(int j = 0;j < 4;j++){
                if(line[j] == '+')  st += 1 << get(i,j);//状态压缩
            }
        }
        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);//改变第i行状态
                    change[i][j] += 1 << get(k,j);//改变第j列状态
                }
                change[i][j] -= 1 << get(i,j);//恢复重复改变的状态
            }
        }
        vector<PII> res;
        for(int k = 0;k < 1 << 16;k++){//枚举所有可能的解法
            int now = st;
            vector<PII> path;
            for(int i = 0;i < 16;i++){
                if(k >> i & 1){
                    int x = i / 4,y = i % 4;
                    now ^= change[x][y];
                    path.push_back({x,y});
                }
            }
            if(!now && (res.empty()|| res.size() > path.size()))    res = path;
            }
        cout<<res.size()<<endl;
        for(auto x : res)   cout<<x.first + 1<<" "<<x.second + 1<<endl;
        return 0;
    }
    
    • 1

    信息

    ID
    27
    时间
    1000ms
    内存
    128MiB
    难度
    3
    标签
    递交数
    160
    已通过
    82
    上传者