题解 | 小红的战争棋盘

巨型模拟题。

使用路径压缩合并并查集即可维护领土兼并功能。注意投放军队的时候也会产生冲突，但不输出任何信息。

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

using pii = pair<int, int>;

int n;
int m;
int k;
vector<string> names;
unordered_map<string, int> id;
vector<pii> pos;
vector<int> cntLand;

int q;

vector<int> p;

vector<vector<int>> grid;

int P(int a) {
    if (p[a] == a) {
        return a;
    }
    return p[a] = P(p[a]);
}

bool Cmp(int a, int b) {
    return cntLand[a] < cntLand[b] || cntLand[a] == cntLand[b] &&
           names[a] < names[b];
}

void Eat(int a, int b, bool show = true) {
    p[b] = a;
    id.erase(names[b]);
    if (show) {

        cntLand[a] += cntLand[b];
        cout << names[a] << " wins!\n";
        // cout << "eat " << names[b] << endl;
    }
}

void Battle(int a, int b, bool show = true) {
    if (Cmp(a, b)) {
        Eat(b, a, show);
        return;
    }
    Eat(a, b, show);
}

void Solve() {
    cin >> n >> m >> k;
    pos.resize(k);
    p.resize(k);
    names.resize(k);
    grid.assign(n, vector<int>(m, -1));
    cntLand.assign(k, 1);
    for (int i = 0; i < k; i++) {
        auto& str = names[i];
        auto& [x, y] = pos[i];
        cin >> str >> x >> y;
        x--;
        y--;
        id[str] = i;
        p[i] = i;
        if (grid[x][y] != -1) {
            Battle(P(grid[x][y]), i, false);
            continue;
        }
        grid[x][y] = i;
    }
    cin >> q;
    string str;
    char c;
    while (q--) {
        cin >> str >> c;
        auto it = id.find(str);
        if (it == id.end()) {
            cout << "unexisted empire.\n";
            continue;
        }
        int idx = it->second;
        auto [x, y] = pos[idx];
        switch (c) {
            case 'W':
                x--;
                break;
            case 'S':
                x++;
                break;
            case 'A':
                y--;
                break;
            default:
                y++;
                break;
        }
        if (x < 0 || x >= n || y < 0 || y >= m) {
            cout << "out of bounds!\n";
            continue;
        }
        pos[idx] = {x, y};
        int& t = grid[x][y];
        // cout << x << ',' << y << ',' << t << endl;
        if (t == -1) {
            t = idx;
            cntLand[idx]++;
            cout << "vanquish!\n";
            continue;
        }
        t = P(t);
        // cout << t << ',' << idx << endl;
        if (t == idx) {
            cout << "peaceful.\n";
            continue;
        }
        Battle(idx, t);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
    return 0;
}