Special Moves#11804
Problem Author: | Hasan Saleh (MathModel) |
Prepared by: | Hasan Saleh (MathModel) |
Edited by: | Hasan Saleh (MathModel) |
We can maintain a map of pairs to integers, i.e., \mathtt{map<pair<int,int>,int>}, so that we can keep track of the number of visits for each pair of coordinates. After that, we go through the values of the map and check the maximum number of visits (let's say this is ). Then we go through the keys of the map and count how many mp[\{x,y\}]=m, and this will be the final answer.
Complexity O(n \log n).
#include <bits/stdc++.h>
using namespace std;
int solve(){
int n,x,y;cin>>n>>x>>y;
map<pair<int,int>,int>mp;
string s;cin>>s;
mp[{x,y}]++;
for(auto i:s){
if(i=='R'){
x++;
}
if(i=='L'){
x--;
}
if(i=='U'){
y++;
}
if(i=='D'){
y--;
}
mp[{x,y}]++;
}
int mx=0;int ans=0;
for(auto i:mp)mx=max(mx,i.second);
for(auto i:mp){
if(i.second==mx)ans++;
}
cout<<ans<<"\n";
return 0;
}
int main(){
int t;cin>>t;
while(t--){
solve();
}
return 0;
}