2 条题解

  • 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;
    }
    
    • 0
      @ 2024-11-19 19:39:36
      #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);
                      change[i][j] += 1 << get(k,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
      标签
      递交数
      164
      已通过
      85
      上传者