Movimientos Especiales#11804
Autor del Problema: | Hasan Saleh (MathModel) |
Preparado por: | Hasan Saleh (MathModel) |
Editado por: | Hasan Saleh (MathModel) |
Podemos mantener un mapa de pares a enteros, es decir, \mathtt{map<pair<int,int>,int>}, para que podamos hacer un seguimiento del número de visitas para cada par de coordenadas. Después de eso, pasamos por los valores del mapa y verificamos el número máximo de visitas (digamos que esto es ). Luego pasamos por las claves del mapa y contamos cuántos mp[\{x,y\}]=m, y esta será la respuesta final.
Complejidad 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;
}