比赛 |
国庆欢乐赛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;
}