记录编号	607122	评测结果	AAAAAAAAAATTTTT
题目名称	3863.[USACO23 Jan Silver] Following Directions	最终得分	67
用户昵称	KKZH	是否通过	未通过
代码语言	C++	运行时间	27.077 s
提交时间	2025-10-05 17:19:14	内存使用	152.05 MiB

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+10;
int n,qq;
char dis[N][N];
int food[N][2];
struct node{
    int x,y;
}to[N][N];
vector <node> ed[N][N];
queue <node> q;
signed main(){
    freopen("zunxun.in","r",stdin);
    freopen("zunxun.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    string s;
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int j=1;j<=n;j++){
            dis[i][j]=s[j-1]; 
            to[i][j]={i,j};
            if(dis[i][j]=='R'){
                ed[i][j+1].push_back({i,j});
                to[i][j]={i,j+1};
            }
            else{
                ed[i+1][j].push_back({i,j});
                to[i][j]={i+1,j};
            }
        }
        cin>>food[i][0];//0为横 
//        cout<<food[1][0]<<endl;
    }
    for(int i=1;i<=n;i++){
        cin>>food[i][1];//1为竖 
//        cout<<food[i][1];
    }
    int tot=0;
    for(int i=n;i>=1;i--){//0
//        if(dis[i-1][j]=='D'||dis[i][j-1]=='R') continue;
        int cnt=0;
        q.push({i,n+1});
        while(!q.empty()){
            cnt++;
            node x=q.front();
            q.pop();
            for(int k=0;k<ed[x.x][x.y].size();k++){
                node y=ed[x.x][x.y][k];
                q.push(y);
            }
        }
        cnt--;
//            cnt--;
//        if(x==n+1) tot+=cnt*food[y][1];
        tot+=cnt*food[i][0];
//    cerr<<tot<<endl;
//            cout<<x<<" "<<y<<" "<<((x==n+1)?food[y][1]:food[x][0])<<endl;
    }
    for(int i=n;i>=1;i--){//1
//        if(dis[i-1][j]=='D'||dis[i][j-1]=='R') continue;
        int cnt=0;
        q.push({n+1,i});
        while(!q.empty()){
            cnt++;
            node x=q.front();
            q.pop();
            for(int k=0;k<ed[x.x][x.y].size();k++){
                node y=ed[x.x][x.y][k];
                q.push(y);
            }
        }
        cnt--;
//        if(x==n+1) tot+=cnt*food[y][1];
        tot+=cnt*food[i][1];
//            cout<<x<<" "<<y<<" "<<((x==n+1)?food[y][1]:food[x][0])<<endl;
    }
    cin>>qq;
    cout<<tot<<endl;
    int x,y;
    for(int i=1;i<=qq;i++){
        cin>>x>>y;
        int p1=0,p2=0;
        int x1=x,y1=y;
        while(x1!=n+1&&y1!=n+1){
            int tx,ty;
            tx=to[x1][y1].x;
            ty=to[x1][y1].y;
            x1=tx,y1=ty;
        }
        if(x1==n+1) p1=food[y1][1];
        else p1=food[x1][0];
//        cout<<dis[1][1]<<endl;
        if(dis[x][y]=='D'){
//        cout<<1;
            dis[x][y]='R';
            to[x][y]={x,y+1};
            ed[x][y+1].push_back({x,y});
            int now=0;
            for(int j=0;j<ed[x+1][y].size();j++){
                if(ed[x+1][y][j].x==x&&ed[x+1][y][j].y==y){
                    now=j;
                    break;
                }
            }
//            cout<<ed[x+1][y].size()<<endl;
            ed[x+1][y].erase(ed[x+1][y].begin()+now);
        }else{
            dis[x][y]='D';
            to[x][y]={x+1,y};
            ed[x+1][y].push_back({x,y});
            int now;
            for(int j=0;j<ed[x][y+1].size();j++){
                if(ed[x][y+1][j].x==x&&ed[x][y+1][j].y==y){
                    now=j;
                    break;
                }
            }
            ed[x][y+1].erase(ed[x][y+1].begin()+now);
        }
        x1=x,y1=y;
        while(x1!=n+1&&y1!=n+1){
            int tx,ty;
            tx=to[x1][y1].x;
            ty=to[x1][y1].y;
            x1=tx,y1=ty;
        }
        if(x1==n+1) p2=food[y1][1];
        else p2=food[x1][0];
        q.push({x,y});
        int cnt=0;
        while(!q.empty()){
            cnt++;
            node x=q.front();
            q.pop();
            for(int j=0;j<ed[x.x][x.y].size();j++){
                node y=ed[x.x][x.y][j];
                q.push(y);
            }
        }
        tot+=(p2-p1)*cnt;
        cout<<tot<<endl;
    }
}