网易互娱 8.27 笔试题解

// 第1题
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    int T;
    while (cin >> T) {
        int N, M;
        for (int t = 0; t < T; ++t) {
            cin >> N >> M;
            vector<vector<char>> v(N, vector<char>(N));
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N; ++j) cin >> v[i][j];
            }

            if (M <= N) {
                int idx = (N - M) / 2;
                for (int i = idx; i < N - idx; ++i) {
                    for (int j = idx; j < N - idx; ++j) {
                        cout << v[i][j];
                    }
                    cout << endl;
                }
                if (t != T - 1) cout << endl;
            } else {
                float left = (float(M - N)) / 2 / N;
                int times = ceil(left) * 2 + 1;
                times *= N;
                vector<vector<char>> wall(times, vector<char>(times));
                for (int i = 0; i < times; ++i) {
                    for (int j = 0; j < times; ++j) {
                        wall[i][j] = v[i%N][j%N];
                    }
                }
                int center = ceil(times / 2);
                int width = ceil(M / 2);
                for (int i = center - width; i <= center + width; ++i) {
                    for (int j = center - width; j <= center + width; ++j) {
                        cout << wall[i][j];
                    }
                    cout << endl;
                }
                if (t != T - 1) cout << endl;
            }
        }
    }
    return 0;
}

// 第2题
#include <iostream>
#include <vector>
#include <set>
using namespace std;

bool is_intersect(const vector<int>& a, const vector<int>& b) {
    int xmin = max(a[0], b[0]);
    int xmax = min(a[2], b[2]);
    int ymin = max(a[1], b[1]);
    int ymax = min(a[3], b[3]);
    return (xmin < xmax && ymin < ymax);
}

int main() {
    int T;
    while (cin >> T) {
        int N;
        for (int t = 0; t < T; ++t) {
            cin >> N;
            vector<vector<int>> v;
            int x0, y0, x1, y1;
            for (int i = 0; i < N; ++i) {
                cin >> x0 >> y0 >> x1 >> y1;
                v.push_back({x0, y0, x1, y1});
            }
            if (N == 1) {
                cout << 0;
                if (t != T - 1) cout << endl;
                continue;
            }

            set<vector<int>> ss;
            for (int i = 0; i < N; ++i) {
                for (int j = i + 1; j < N; ++j) {
                    if (is_intersect(v[i], v[j])) {
                        ss.emplace(v[i]);
                        ss.emplace(v[j]);
                    }
                }
            }

            if (ss.empty()) {
                cout << 0;
                if (t != T - 1) cout << endl;
                continue;
            }

            int res = 0;
            vector<vector<int>> grid(1005, vector<int>(1005, 0));
            for (auto it = ss.begin(); it != ss.end(); ++it) {
                for (int i = (*it)[0]; i < (*it)[2]; ++i) {
                    for (int j = (*it)[1]; j < (*it)[3]; ++j) {
                        if (grid[i][j] == 0) {
                            ++res;
                        }
                        grid[i][j] = 1;
                    }
                }
            }
            cout << res;
            if (t != T - 1) cout << endl;
        }
    }
    return 0;
}

// 第3题
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// 构造 string，24位可以用int，用哈希表缓存
/*
   -  -
  |\/|/\|
   -  -
  |\/|\/|
   _  _
   前8位代表边框，后12位代表内部，还有8位是陡的斜线
*/

int connect(int x, int y, int nx, int ny) {
    if (x < nx) {
        swap(x, nx);
        swap(y, ny);
    }
    if (x == 0) {
        if (y == 0) {
            if (nx == 0 && ny == 1) return (1 << 1);
            else if (nx == 0 && ny == 2) return (1 << 1) | (1 << 2);
            else if (nx == 1 && ny == 0) return (1 << 8);
            else if (nx == 2 && ny == 0) return (1 << 7) | (1 << 8);
            else if (nx == 1 && ny == 1) return (1 << 9);
            else if (nx == 1 && ny == 2) return (1 << 17);
            else if (nx == 2 && ny == 1) return (1 << 24);
            else if (nx == 2 && ny == 2) return (1 << 9) | (1 << 13);
        } else if (y == 1) {
            if (nx == 0 && ny == 0) return (1 << 1);
            else if (nx == 0 && ny == 2) return (1 << 2);
            else if (nx == 1 && ny == 0) return (1 << 28);
            else if (nx == 1 && ny == 1) return (1 << 10);
            else if (nx == 1 && ny == 2) return (1 << 25);
            else if (nx == 2 && ny == 0) return (1 << 18);
            else if (nx == 2 && ny == 1) return (1 << 10) | (1 << 14);
            else if (nx == 2 && ny == 2) return (1 << 19);
        } else if (y == 2) {
            if (nx == 0 && ny == 0) return (1 << 1) | (1 << 2);
            else if (nx == 0 && ny == 1) return (1 << 2);
            else if (nx == 1 && ny == 0) return (1 << 20);
            else if (nx == 1 && ny == 1) return (1 << 11);
            else if (nx == 1 && ny == 2) return (1 << 3);
            else if (nx == 2 && ny == 0) return (1 << 11) | (1 << 15);
            else if (nx == 2 && ny == 1) return (1 << 21);
            else if (nx == 2 && ny == 2) return (1<<3) | (1<<4);
        }
    } else if (x == 1) {
        if (y == 0) {
            if (nx == 0 && ny == 0) return (1 << 8);
            else if (nx == 0 && ny == 1) return (1 << 28);
            else if (nx == 0 && ny == 2) return (1 << 20);
            else if (nx == 1 && ny == 1) return (1 << 16);
            else if (nx == 1 && ny == 2) return (1 << 12) | (1 << 16);
            else if (nx == 2 && ny == 0) return (1 << 7);
            else if (nx == 2 && ny == 1) return (1 << 27);
            else if (nx == 2 && ny == 2) return (1 << 23);
        } else if (y == 1) {
            if (nx == 0 && ny == 0) return (1 << 9);
            else if (nx == 0 && ny == 1) return (1 << 10);
            else if (nx == 0 && ny == 2) return (1 << 11);
            else if (nx == 1 && ny == 0) return (1 << 16);
            else if (nx == 1 && ny == 2) return (1 << 12);
            else if (nx == 2 && ny == 0) return (1 << 15);
            else if (nx == 2 && ny == 1) return (1 << 14);
            else if (nx == 2 && ny == 2) return (1 << 13);
        } else if (y == 2) {
            if (nx == 0 && ny == 0) return (1 << 17);
            else if (nx == 0 && ny == 1) return (1 << 25);
            else if (nx == 0 && ny == 2) return (1 << 3);
            else if (nx == 1 && ny == 0) return (1 << 16) | (1 << 12);
            else if (nx == 1 && ny == 1) return (1 << 12);
            else if (nx == 2 && ny == 0) return (1 << 22);
            else if (nx == 2 && ny == 1) return (1 << 26);
            else if (nx == 2 && ny == 2) return (1 << 4);
        }
    } else {
        if (y == 0) {
            if (nx == 0 && ny == 0) return (1 << 7) | (1 << 8);
            else if (nx == 0 && ny == 1) return (1 << 18);
            else if (nx == 0 && ny == 2) return (1 << 15) | (1 << 11);
            else if (nx == 1 && ny == 0) return (1 << 7);
            else if (nx == 1 && ny == 1) return (1 << 15);
            else if (nx == 1 && ny == 2) return (1 << 22);
            else if (nx == 2 && ny == 1) return (1 << 6);
            else if (nx == 2 && ny == 2) return (1 << 5) | (1 << 6);
        } else if (y == 1) {
            if (nx == 0 && ny == 0) return (1 << 24);
            else if (nx == 0 && ny == 1) return (1 << 10) | (1 << 14);
            else if (nx == 0 && ny == 2) return (1 << 21);
            else if (nx == 1 && ny == 0) return (1 << 27);
            else if (nx == 1 && ny == 1) return (1 << 14);
            else if (nx == 1 && ny == 2) return (1 << 26);
            else if (nx == 2 && ny == 0) return (1 << 6);
            else if (nx == 2 && ny == 2) return (1 << 5);
        } else if (y == 2) {
            if (nx == 0 && ny == 0) return (1 << 9) | (1 << 13);
            else if (nx == 0 && ny == 1) return (1 << 19);
            else if (nx == 0 && ny == 2) return (1 << 3) | (1 << 4);
            else if (nx == 1 && ny == 0) return (1 << 23);
            else if (nx == 1 && ny == 1) return (1 << 13);
            else if (nx == 1 && ny == 2) return (1 << 4);
            else if (nx == 2 && ny == 1) return (1 << 5);
            else if (nx == 2 && ny == 0) return (1 << 5) | (1 << 6);
        }
    }
    return 0;
}

void dfs(int x, int y, int cur, vector<vector<char>> &grid, unordered_set<int> &ss) {
    grid[x][y] = 'X';
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (grid[i][j] == '.') {
                int val = connect(x, y, i, j);
                int nex = cur | val;
                ss.emplace(nex);
                dfs(i, j, nex, grid, ss);
            }
        }
    }
    grid[x][y] = '.';
}

int main() {
    int T;
    while (cin >> T) {
        for (int t = 0; t < T; ++t) {
            vector<vector<char>> v(3, vector<char>(3));
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) cin >> v[i][j];
            }

            unordered_set<int> ss;

            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    if (v[i][j] == '.') dfs(i, j, 0, v, ss);
                }
            }
            cout << ss.size();
            if (t != T - 1) cout << endl;
        }
    }
    return 0;
}