Özel Hareketler#11804
Problem Yazarı: | Hasan Saleh (MathModel) |
Hazırlayan: | Hasan Saleh (MathModel) |
Düzenleyen: | Hasan Saleh (MathModel) |
Her koordinat çifti için ziyaret sayısını takip edebilmek için bir çiftleri tam sayılara harita tutabiliriz, yani \mathtt{map<pair<int,int>,int>}. Sonrasında, haritanın değerlerini geçip en yüksek ziyaret sayısını kontrol ederiz (bunu olarak adlandıralım). Ardından, haritanın anahtarlarını geçip kaç tane mp[\{x,y\}]=m olduğunu sayarız ve bu, nihai cevap olacaktır.
Karmaşıklık 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;
}