Xüsusi Hərəkətlər#11804
Problem Müəllifi: | Hasan Saleh (MathModel) |
Hazırlayan: | Hasan Saleh (MathModel) |
Redaktə edən: | Hasan Saleh (MathModel) |
Biz cütləri tam ədədlərə xəritə saxlaya bilərik, yəni \mathtt{map<pair<int,int>,int>}, beləliklə hər koordinat cütü üçün ziyarətlərin sayını izləyə bilərik. Bundan sonra xəritənin dəyərlərini keçərək maksimum ziyarət sayını (gəlin bunu adlandıraq) yoxlayırıq. Sonra xəritənin açarlarını keçərək mp[\{x,y\}]=m olanların sayını sayırıq və bu, son cavab olacaq.
Komplekslik 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;
}