比赛 国庆欢乐赛3 评测结果 AWAWAAAWWWTTTTT
题目名称 Following Directions 最终得分 33
用户昵称 梧叶已同秋雨去 运行时间 15.851 s
代码语言 C++ 内存使用 18.35 MiB
提交时间 2025-10-05 10:19:57
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,a[1505][1505],q;//-1是向下,-2是向右 
int b[1505][1505],h[1505][1505];//1是上,2是左 
long long sum;
int dfs(int x,int y){
    if(x==n+1||y==n+1){
        return a[x][y];
    }
    if(a[x][y]==-1){
        h[x+1][y]+=1;
        if(b[x+1][y]){
            b[x][y]=b[x+1][y];
            return b[x][y];
        }else{
            b[x][y]=dfs(x+1,y);
            return b[x][y];
        }
    }
    if(a[x][y]==-2){
        h[x][y+1]+=2;
        if(b[x][y+1]){
            b[x][y]=b[x][y+1];
            return b[x][y];
        }else{
            b[x][y]=dfs(x,y+1);
            return b[x][y];
        }
        
    }
}
void hdfs(int x,int y){
    // printf("(%d,%d)\n",x,y);
    if(h[x][y]==1){
        sum+=b[x][y]-b[x-1][y];
        b[x-1][y]=b[x][y];
        hdfs(x-1,y);
    }
    if(h[x][y]==2){
        sum+=b[x][y]-b[x][y-1];
        b[x][y-1]=b[x][y];
        hdfs(x,y-1);
    }
    if(h[x][y]==3){
       sum+=b[x][y]-b[x-1][y];
       b[x-1][y]=b[x][y];
       sum+=b[x][y]-b[x][y-1];
       b[x][y-1]=b[x][y];
       hdfs(x-1,y);
       hdfs(x,y-1);
    }
    if(h[x][y]==0){
        return;
    }
}
int main(){
    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)continue;
            if(i<=n&&j<=n){
                char x;
                cin>>x;
                if(x=='D'){
                    a[i][j]=-1;
                }
                if(x=='R'){
                    a[i][j]=-2;
                }
            }else{
                cin>>a[i][j];
            }
        }
    }
//    for(int i=1;i<=n+1;i++){
//        for(int j=1;j<=n+1;j++){
//            cout<<a[i][j]<<" ";
//        }cout<<endl;
//    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(b[i][j])continue;
            b[i][j]=dfs(i,j);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            sum+=b[i][j];
        }
    }cout<<sum<<"\n";
    cin>>q;
    while(q--){
        int x;int y;
        cin>>x>>y;
//        printf("h[i][j]:%d\n",h[x][y]);
        if(a[x][y]==-1){
            a[x][y]=-2;
            sum+=b[x][y+1]-b[x][y];
            h[x+1][y]-=1;
            h[x][y+1]+=2;
            b[x][y]=b[x][y+1];
            hdfs(x,y);
        }else{
            a[x][y]=-1;
            sum+=b[x+1][y]-b[x][y];
            h[x+1][y]+=1;
            h[x][y+1]-=2;
            b[x][y]=b[x+1][y];
            hdfs(x,y);
        }
        cout<<sum<<"\n";
    }
    return 0;
}