A1770 [USACO24DEC] 2D Conveyer Belt S

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    int V = N * N;
    vector<char> dir(V, '?');              // 每个格子的传送带方向
    vector<pair<int, int>> built(Q);
    for (int i = 0; i < Q; i++) {
        int r, c;
        char t;
        cin >> r >> c >> t;
        --r; --c;
        dir[r * N + c] = t;
        built[i] = {r, c};
    }

    const int dx[4] = {-1, 0, 1, 0};
    const int dy[4] = {0, 1, 0, -1};
    auto border = [&](int x, int y) { return x == 0 || y == 0 || x == N - 1 || y == N - 1; };
    // 固定格子的传送带指向的格子；出界返回 -1
    auto target = [&](int x, int y) {
        char t = dir[x * N + y];
        int nx = x, ny = y;
        if (t == 'L') ny--;
        else if (t == 'R') ny++;
        else if (t == 'U') nx--;
        else nx++;
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) return -1;
        return nx * N + ny;
    };

    // esc[x] = 该格子能走出方阵；cnt = 能逃走的格子数
    vector<char> esc(V, 0);
    queue<int> que;
    int cnt = 0;
    auto add = [&](int x) {
        if (esc[x]) return;
        esc[x] = 1;
        cnt++;
        que.push(x);
    };
    // 传播：y 能逃走，则 y 的 '?' 邻居、以及指向 y 的固定格子都能逃走
    auto propagate = [&]() {
        while (!que.empty()) {
            int y = que.front();
            que.pop();
            int yy = y / N, yx = y % N;
            for (int d = 0; d < 4; d++) {
                int nx = yy + dx[d], ny = yx + dy[d];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                int nid = nx * N + ny;
                if (esc[nid]) continue;
                if (dir[nid] == '?') add(nid);
                else if (target(nx, ny) == y) add(nid);
            }
        }
    };

    // 初始：全部建完之后，能一步走出方阵的格子
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            int id = x * N + y;
            if (dir[id] == '?') {
                if (border(x, y)) add(id);
            } else {
                if (target(x, y) == -1) add(id);
            }
        }
    }
    propagate();

    vector<int> ans(Q + 1);
    ans[Q] = V - cnt;

    // 逆序拆掉传送带：能逃走的格子只会变多
    for (int d = Q; d >= 2; d--) {
        int x = built[d - 1].first, y = built[d - 1].second;
        dir[x * N + y] = '?';
        if (!esc[x * N + y]) {
            bool can = border(x, y);
            for (int k = 0; k < 4 && !can; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if (esc[nx * N + ny]) can = true;
            }
            if (can) {
                add(x * N + y);
                propagate();
            }
        }
        ans[d - 1] = V - cnt;
    }

    for (int d = 1; d <= Q; d++) cout << ans[d] << '\n';
    return 0;
}