比赛 国庆欢乐赛3 评测结果 AAAAAAATTTTTTTT
题目名称 Following Directions 最终得分 47
用户昵称 zhyn 运行时间 24.520 s
代码语言 C++ 内存使用 15.80 MiB
提交时间 2025-10-05 11:19:23
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;

#define maxn 3000

#define ll long long

int n,t;
bool vis[maxn][maxn];
ll a[maxn],b[maxn];
int l[maxn],r[maxn];
int p[maxn];
ll cnt=0;


struct node{
    int x,y;
};
queue<node>q;
ll ans=0;

void bfs(){
    ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            q.push({i,j});
        }
    }
    
    while(!q.empty()){
        int x=q.front().x,y=q.front().y;
        q.pop();
        if(x==n+1){
            ans+=b[y];
            continue;
        }
        if(y==n+1){
            ans+=a[x];
            continue;
        }
        if(vis[x][y]){
            q.push({x,y+1});
        }
        else{
            q.push({x+1,y});
        }
    }
    
}
void solv(int x,int y){
    if(x-1!=0&&!vis[x-1][y]){
        cnt++;
        solv(x-1,y);
    }
    if(y-1!=0&&vis[x][y-1]){
        cnt++;
        solv(x,y-1);
    }
}

void sol(int s){
    int x=l[s],y=r[s];
    ll sum;
    while(x!=n+1&&y!=n+1){
        if(vis[x][y]){
            y++;
        }
        else{
            x++;
        }
    }
    if(x==n+1){
        sum=b[y];
    }
    else{
        sum=a[x];
    }
    x=l[s],y=r[s];
    cnt=1;
    solv(x,y);
    ans-=sum*cnt; 
    vis[l[s]][r[s]]^=1;
    x=l[s],y=r[s];
    sum=0;
    while(x!=n+1&&y!=n+1){
        if(vis[x][y]){
            y++;
        }
        else{
            x++;
        }
    }
    
    if(x==n+1){
        sum=b[y];
    }
    else{
        sum=a[x];
    }
    ans+=sum*cnt;
    cout<<ans<<"\n";
}

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;i++){
        char s;
        for(int j=1;j<=n;j++){
            cin>>s;
            if(s=='R'){
                vis[i][j]=1;
            }
            else{
                vis[i][j]=0;
            }
        }
        cin>>a[i];
    }
    
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    
    cin>>t;
    
    
    
    for(int i=1;i<=t;i++){
        int x,y;
        cin>>x>>y;
        l[i]=x,r[i]=y;
    }
    
    
    bfs();
    cout<<ans<<"\n";
    for(int i=1;i<=t;i++){
        sol(i);
    }
    
    
    return 0;
}