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