题意
N*M的网格,一辆车沿着网格线按给定路线走,每个网格里有一个人,人的视线始终看着车,问这些人净转圈数的平方和。
分析
由于车的起点和终点都为左上角,且每个格子里的人永远面对着车,经过多次模拟可发现:每个人的圈数与其所在格子左边向下次数与向上次数的差。于是只需要维护这个次数,对每次行车路线上的右边的格做处理,可以用前缀和的思想来维护,而且因为网格具体规格不确定,可以用vector。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <ctype.h>
#include <queue>
using namespace std;
const int maxn=1e6+;
const int inf=0x3f3f3f3f;
const int mod=1e9+;
typedef long long ll;
vector< vector<int> >v;
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif
int t, m, n, k;
int kase=;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&k);
int dx=,dy=;
int d;
char dir[];
v=vector< vector<int> >(n+,vector<int>(m+,));
while(k--){
scanf("%s%d",dir,&d);
if(dir[]=='L'){
dy-=d;
}else if(dir[]=='R'){
dy+=d;
}else if(dir[]=='D'){
v[dx][dy]++;
v[dx+d][dy]--;
dx+=d;
}else if(dir[]=='U'){
v[dx][dy]++;
v[dx-d][dy]-=;
dx-=d;
}
} // for(int i=1;i<=n+1;i++){
// for(int j=1;j<=m+1;j++)
// printf("%d",v[i][j]);
// puts("");
// }
ll ans=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
v[i][j]+=v[i-][j]+v[i][j-]-v[i-][j-];
ans+=(ll)v[i][j]*v[i][j];
}
}
printf("Case #%d: %lld\n",++kase,ans);
}
return ;
}