比赛 |
国庆欢乐赛3 |
评测结果 |
AAAAAAATTTTTTTT |
题目名称 |
Following Directions |
最终得分 |
47 |
用户昵称 |
梦那边的美好BP |
运行时间 |
21.221 s |
代码语言 |
C++ |
内存使用 |
18.06 MiB |
提交时间 |
2025-10-05 10:32:41 |
显示代码纯文本
#include <iostream>
#include <utility>
using namespace std;
const int N=1503;
typedef pair<int,int> pii;
int c[N][N],nc[N],cn[N];
pii to[N][N];
int tn[N],nt[N];
int n,q;
void dfs(int x,int y) {
if(x==n+1||y==n+1) {
to[x][y].first=x;
to[x][y].second=y;
return;
}
if(c[x][y]=='R') {
if(to[x][y+1].first==0) {
dfs(x,y+1);
}
to[x][y]=to[x][y+1];
} else {
if(to[x+1][y].first==0) {
dfs(x+1,y);
}
to[x][y]=to[x+1][y];
}
if(to[x][y].first==n+1) nt[to[x][y].second]++;
else tn[to[x][y].first]++;
}
void dfs2(int x,int y) {
// cout<<x<<" " <<y<<endl;
if(x==0||y==0) {
return;
}
// cout<<"-{"<<to[x][y].first<<","<<to[x][y].second<<"}\n";
if(to[x][y].first==n+1) nt[to[x][y].second]--;
else tn[to[x][y].first]--;
if(c[x][y]=='R') {
to[x][y]=to[x][y+1];
} else {
to[x][y]=to[x+1][y];
}
// cout<<"+{"<<to[x][y].first<<","<<to[x][y].second<<"}\n";
if(to[x][y].first==n+1) nt[to[x][y].second]++;
else tn[to[x][y].first]++;
if(c[x][y-1]=='R') {
dfs2(x,y-1);
}
if(c[x-1][y]=='D') {
dfs2(x-1,y);
}
}
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) break;
char ch;
if(i<=n&&j<=n) {
cin>>ch;
c[i][j]=ch;
} else cin>>c[i][j];
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(to[i][j].first==0) dfs(i,j);
// cout<<"("<<to[i][j].first<<","<<to[i][j].second<<")"<<" ";
}
// cout<<endl;
}
int ans=0;
for(int i=1; i<=n; i++) {
// cout<<nt[i]<<" "<<c[n+1][i]<<endl;
ans+=nt[i]*c[n+1][i];
// cout<<tn[i]<<" "<<c[i][n+1]<<endl;
ans+=tn[i]*c[i][n+1];
}
cout<<ans<<endl;
cin>>q;
while(q--) {
int a,b;
cin>>a>>b;
if(c[a][b]=='R') {
c[a][b]='D';
} else {
c[a][b]='R';
}
dfs2(a,b);
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(to[i][j].first==0) dfs(i,j);
// cout<<"("<<to[i][j].first<<","<<to[i][j].second<<")"<<" ";
}
// cout<<endl;
}
ans=0;
for(int i=1; i<=n; i++) {
// cout<<n+1<<" "<<i<<" "<<nt[i]<<endl;
ans+=nt[i]*c[n+1][i];
// cout<<i<<" "<<n+1<<" "<<tn[i]<<endl;
ans+=tn[i]*c[i][n+1];
}
cout<<ans<<endl;
}
return 0;
}