Mouvements Spéciaux#11804
Auteur du Problème: | Hasan Saleh (MathModel) |
Préparé par: | Hasan Saleh (MathModel) |
Édité par: | Hasan Saleh (MathModel) |
Nous pouvons maintenir une carte de paires à des entiers, c'est-à-dire \mathtt{map<pair<int,int>,int>}, afin de suivre le nombre de visites pour chaque paire de coordonnées. Après cela, nous parcourons les valeurs de la carte et vérifions le nombre maximum de visites (appelons cela ). Ensuite, nous parcourons les clés de la carte et comptons combien de mp[\{x,y\}]=m, et cela sera la réponse finale.
Complexité 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;
}