网易互娱8.27笔试第三题c++

set<set<set<pair<int, int>>>> charts;

// 转换函数，将点的列表list转换为无向边的集合，一个这样的集合表示一个“图形”，用set表示，方便统计有多少种这样的“图形”
set<set<pair<int, int>>> func3(vector<pair<int, int>>& list) {
    set<set<pair<int, int>>> res;
    pair<int, int> cur = list[0];
    for (int i=1; i<list.size(); i++) {
        int x = cur.first, y = cur.second;
        pair<int, int> nex = list[i];
        int dx = nex.first, dy = nex.second;
        if (x == dx && dy == y+2) {
            set<pair<int, int>> edge;
            edge.insert({x, y});
            edge.insert({x, y+1});
            res.insert(edge);
            set<pair<int, int>> edge2;
            edge2.insert({dx, dy});
            edge2.insert({x, y+1});
            res.insert(edge2);
        } else if (x == dx && dy == y-2) {
            //temp.insert({x, y-1});
            set<pair<int, int>> edge;
            edge.insert({x, y});
            edge.insert({x, y-1});
            res.insert(edge);
            set<pair<int, int>> edge2;
            edge2.insert({dx, dy});
            edge2.insert({x, y-1});
            res.insert(edge2);
        } else if (y == dy && dx == x+2) {
            set<pair<int, int>> edge;
            edge.insert({x, y});
            edge.insert({x+1, y});
            res.insert(edge);
            set<pair<int, int>> edge2;
            edge2.insert({dx, dy});
            edge2.insert({x+1, y});
            res.insert(edge2);
            //temp.insert({x+1, y});
        } else if (y == dy && dx == x-2) {
            //temp.insert({x-1, y});
            set<pair<int, int>> edge;
            edge.insert({x, y});
            edge.insert({x-1, y});
            res.insert(edge);
            set<pair<int, int>> edge2;
            edge2.insert({dx, dy});
            edge2.insert({x-1, y});
            res.insert(edge2);
        } else if (dx == x+2 && dy == y+2
                  || dx == x+2 && dy == y-2
                  || dx == x-2 && dy == y+2
                  || dx == x-2 && dy == y-2) {
            //temp.insert({1, 1});
            set<pair<int, int>> edge;
            edge.insert({x, y});
            edge.insert({1, 1});
            res.insert(edge);
            set<pair<int, int>> edge2;
            edge2.insert({dx, dy});
            edge2.insert({1, 1});
            res.insert(edge2);
        } else {
            set<pair<int, int>> edge;
            edge.insert({x, y});
            edge.insert({dx, dy});
            res.insert(edge);
        }
        cur = nex;
    }
    return res;
}

// 回溯函数，用list记录选择的点
void func2(vector<pair<int, int>>& list, vector<pair<int, int>>& dot, vector<bool>& visited_dot, int count) {
    int n = dot.size();
    if (count == 0) {
        set<set<pair<int, int>>> chart;
        chart = func3(list);
        charts.insert(chart);
        return;
    }
    for (int i=0; i<n; i++) {
        if (visited_dot[i]) continue;

        list.push_back(dot[i]);
        visited_dot[i] = true;
        func2(list, dot, visited_dot, count-1);
        visited_dot[i] = false;
        list.pop_back();
    }
}

void func(const vector<string>& vi) {
    //set<set<pair<int, int>>> chart;
    vector<pair<int, int>> list;
    vector<pair<int, int>> dot;
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            if (vi[i][j] == '.') {
                dot.push_back({i, j});
            }
        }
    }
    int n = dot.size();
    vector<bool> visited_dot(n, false);
    for (int count=2; count<=n; count++) {
        func2(list, dot, visited_dot, count);
    }
    cout<<charts.size()<<endl;
    // 测试代码
    int xx = 0;
    for (auto it=charts.begin(); it!=charts.end(); it++) {
        vector<vector<char>> v1(3, vector<char>(3, 'x'));
        set<set<pair<int, int>>> chart1 = *it;
        cout<<++xx<<endl;
        for (auto it1=chart1.begin(); it1!=chart1.end(); it1++) {
            set<pair<int, int>> edge1 = *it1;
            for (auto it2=edge1.begin(); it2!=edge1.end(); it2++) {
                cout<<'('<<it2->first<<','<<it2->second<<')'<<';';
            }
            cout<<endl;
        }
        cout<<endl;
    }
}

int main() {
    int T;
    cin>>T;
    vector<vector<string>> vi(T, vector<string>(3));
    for (int i=0; i<T; i++) {
        for (int j=0; j<3; j++) {
            cin>>vi[i][j];
        }
        func(vi[i]);
        cout<<endl;
    }
    return 0;
}