记录编号	607074	评测结果	AAAAAAAAAATTTTT
题目名称	3863.[USACO23 Jan Silver] Following Directions	最终得分	67
用户昵称	梦那边的美好BP	是否通过	未通过
代码语言	C++	运行时间	15.738 s
提交时间	2025-10-05 14:52:47	内存使用	18.06 MiB

#include <iostream>
#include <utility>
using namespace std;
const int N = 1503;
typedef pair<int, int> pii;
int c[N][N], nc[N], cn[N];
pii to[N][N];
int tn[N], nt[N];
int n, q;
void dfs(int x, int y) {
    if (x == n + 1 || y == n + 1) {
        to[x][y].first = x;
        to[x][y].second = y;
        return;
    }
    if (c[x][y] == 'R') {
        if (to[x][y + 1].first == 0) {
            dfs(x, y + 1);
        }
        to[x][y] = to[x][y + 1];
    } else {
        if (to[x + 1][y].first == 0) {
            dfs(x + 1, y);
        }
        to[x][y] = to[x + 1][y];
    }
    if (to[x][y].first == n + 1)
        nt[to[x][y].second]++;
    else
        tn[to[x][y].first]++;
}
void dfs2(int x, int y) {
    if (x == 0 || y == 0)
        return;
    // Clear old counts
    if (to[x][y].first == n + 1)
        nt[to[x][y].second]--;
    else
        tn[to[x][y].first]--;
    to[x][y] = {0, 0}; // Reset path
    dfs(x, y);         // Recompute path for (x, y)
    // Update predecessors
    if (y > 1 && c[x][y - 1] == 'R')
        dfs2(x, y - 1);
    if (x > 1 && c[x - 1][y] == 'D')
        dfs2(x - 1, y);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("zunxun.in", "r", stdin);
    freopen("zunxun.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n + 1; i++) {
        for (int j = 1; j <= n + 1; j++) {
            if (i == n + 1 && j == n + 1)
                break;
            char ch;
            if (i <= n && j <= n) {
                cin >> ch;
                c[i][j] = ch;
            } else
                cin >> c[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (to[i][j].first == 0)
                dfs(i, j);
            //			cout<<"("<<to[i][j].first<<","<<to[i][j].second<<")"<<" ";
        }
        //		cout<<endl;
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        //		cout<<nt[i]<<" "<<c[n+1][i]<<endl;
        ans += nt[i] * c[n + 1][i];
        //		cout<<tn[i]<<" "<<c[i][n+1]<<endl;
        ans += tn[i] * c[i][n + 1];
    }
    cout << ans << endl;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;

        if (c[a][b] == 'R') {
            c[a][b] = 'D';
        } else {
            c[a][b] = 'R';
        }

        dfs2(a, b);

        // for (int i = 1; i <= n; i++) {
        //     for (int j = 1; j <= n; j++) {
        //         if (to[i][j].first == 0)
        //             dfs(i, j);
        //         // cout<<"("<<to[i][j].first<<","<<to[i][j].second<<")"<<"
        //         //";
        //     }
        //     //			cout<<endl;
        // }

        ans = 0;
        for (int i = 1; i <= n; i++) {
            //			cout<<n+1<<" "<<i<<" "<<nt[i]<<endl;
            ans += nt[i] * c[n + 1][i];
            //			cout<<i<<" "<<n+1<<" "<<tn[i]<<endl;
            ans += tn[i] * c[i][n + 1];
        }
        cout << ans << endl;
    }
    return 0;
}