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