比赛 国庆欢乐赛3 评测结果 AAAAAAAAAAAAAAA
题目名称 Following Directions 最终得分 100
用户昵称 梦那边的美好TT 运行时间 1.526 s
代码语言 C++ 内存使用 13.57 MiB
提交时间 2025-10-05 10:55:08
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[1502][1502],b[1502][1502],q,l,r;
ll ans;
string s;
void dfs(int x,int y){
    b[x][y]=1;
    if(!((x>1&&a[x-1][y]==0)||(y>1&&a[x][y-1]==1))) return ;
    if(x>1&&a[x-1][y]==0){
        dfs(x-1,y);
        b[x][y]+=b[x-1][y];
    }
    if(y>1&&a[x][y-1]==1){
        dfs(x,y-1);
        b[x][y]+=b[x][y-1];
    }
    return ;
}
void f1(int x,int y,int num){
    b[x][y]-=num;
    if(x<n&&a[x][y]==0) f1(x+1,y,num);
    if(y<n&&a[x][y]==1) f1(x,y+1,num);
    return ;
}
void f2(int x,int y,int num){
    if(x<n&&a[x][y]==0){
        b[x+1][y]+=num;
        f2(x+1,y,num);
    }
    if(y<n&&a[x][y]==1){
        b[x][y+1]+=num;
        f2(x,y+1,num);
    }
    return ;
}
int main(){
    freopen("zunxun.in","r",stdin);
    freopen("zunxun.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int j=1;j<=n;j++)
        if(s[j-1]=='R') a[i][j]=1;
        cin>>a[i][n+1];
    }
    for(int i=1;i<=n;i++) cin>>a[n+1][i];
    for(int i=1;i<=n;i++){
        if(a[i][n]==1){
            dfs(i,n);
            ans+=b[i][n]*a[i][n+1];
        }
        if(a[n][i]==0){
            dfs(n,i);
            ans+=b[n][i]*a[n+1][i];
        }
    }
    cout<<ans<<endl;
    cin>>q;
    while(q--){
        cin>>l>>r;
        ans=0;
        b[l][r]*=2;
        f1(l,r,b[l][r]/2);
        if(a[l][r]==0) a[l][r]=1;
        else a[l][r]=0;
        f2(l,r,b[l][r]);
        for(int i=1;i<=n;i++){
            if(a[i][n]==1) ans+=b[i][n]*a[i][n+1];
            if(a[n][i]==0) ans+=b[n][i]*a[n+1][i];
        }
        cout<<ans<<endl;
    }
    return 0;
}