题解 | #小红的战争棋盘#

考察知识点：模拟

大模拟题，需要考虑的情况比较多，下面的代码提供了一种写法。

时间复杂度：$O(kq)O(kq)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define N 505

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    int board[N][N] = {0};      // 棋盘，记录领土标号
    int cnt = 0;                // 标号计数
    map<string, pii> pos;       // 记录军队位置
    map<string, int> power;     // 记录军队战力（即领土数量）
    map<string, vi> domain;     // 记录军队占领领土的标号
    map<int, string> belong;    // 记录领土归属
    while (k--)
    {
        string name;
        int x, y;
        cin >> name >> x >> y;
        if (board[x][y] == 0)                   // 投放位置为空地
        {
            board[x][y] = ++cnt;
            belong[cnt] = name;
            pos[name] = {x, y};
            power[name] = 1;
            domain[name].push_back(cnt);
        }
        else if (belong[board[x][y]] < name)    // 投放位置有弱于自己的军队
        {
            string old = belong[board[x][y]];
            pos.erase(old);
            power.erase(old);
            domain.erase(old);
            belong[board[x][y]] = name;
            pos[name] = {x, y};
            power[name] = 1;
            domain[name].push_back(board[x][y]);
        }
    }
    map<char, pii> move = {{'W', {-1, 0}}, {'S', {1, 0}}, {'A', {0, -1}}, {'D', {0, 1}}};
    int q;
    cin >> q;
    while (q--)
    {
        string name;
        char op;
        cin >> name >> op;
        // 势力不存在或已消亡
        if (pos.find(name) == pos.end())
        {
            cout << "unexisted empire." << endl;
            continue;
        }
        pii cur = pos[name];
        pii nxt = {cur.first + move[op].first, cur.second + move[op].second};
        // 目标点越界
        if (nxt.first < 1 || nxt.first > n || nxt.second < 1 || nxt.second > m)
        {
            cout << "out of bounds!" << endl;
            continue;
        }
        // 目标点为空地
        if (board[nxt.first][nxt.second] == 0)
        {
            cout << "vanquish!" << endl;
            board[nxt.first][nxt.second] = board[cur.first][cur.second];
            pos[name] = nxt;
            power[name]++;
            domain[name].push_back(board[nxt.first][nxt.second]);
            continue;
        }
        // 目标点为自己的领土
        else if (belong[board[nxt.first][nxt.second]] == name)
        {
            cout << "peaceful." << endl;
            pos[name] = nxt;
            continue;
        }
        // 目标点为敌方领土
        else
        {
            string enemy = belong[board[nxt.first][nxt.second]];
            // 我方战胜敌方
            if (power[name] > power[enemy] || (power[name] == power[enemy] && name > enemy))
            {
                cout << name << " wins!" << endl;
                pos.erase(enemy);
                power[name] += power[enemy];
                power.erase(enemy);
                while (!domain[enemy].empty())  // 敌方领土归我方所有
                {
                    int tmp = domain[enemy].back();
                    domain[enemy].pop_back();
                    belong[tmp] = name;
                    domain[name].push_back(tmp);
                }
                domain.erase(enemy);
                board[nxt.first][nxt.second] = board[cur.first][cur.second];
                pos[name] = nxt;
                continue;
            }
            // 我方战败
            else
            {
                cout << enemy << " wins!" << endl;
                pos.erase(name);
                power[enemy] += power[name];
                power.erase(name);
                while (!domain[name].empty())  // 我方领土归敌方所有
                {
                    int tmp = domain[name].back();
                    domain[name].pop_back();
                    belong[tmp] = enemy;
                    domain[enemy].push_back(tmp);
                }
                domain.erase(name);
                continue;
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}