Yet Another Walking Robot
原题链接:https://codeforces.com/contest/1296
比赛时没想出来咋做,跳过去了,做了D。(D题比C题水)
主要是不知道怎样存两个数,用二维数组开不了这么大的空间
代码:
#include <bits/stdc++.h>
using namespace std;
map<pair<int,int>,int> Map;
struct qq
{
int l,r;
}q[200010];
int main()
{
int t,n;
string s;
cin>>t;
while(t--)
{
Map.clear(); /////////////////
cin>>n;
cin>>s;
int zx=0,zy=0,cnt=1;
Map[{0,0}]=cnt++;
int ans=99999999,op=0;
for(int i=0;i<n;i++)
{
if(s[i]=='L')
{zx--;}
if(s[i]=='R')
{zx++;}
if(s[i]=='U')
{zy++;}
if(s[i]=='D')
{zy--;}
if(Map[{zx,zy}]==0)
{Map[{zx,zy}]=cnt++;
continue;}
if(Map[{zx,zy}]!=0)
{
q[op].r=i+1;
q[op].l=i+2-(cnt-Map[{zx,zy}]);
op++;
ans=min(ans,cnt-Map[{zx,zy}]);
Map[{zx,zy}]=cnt++;
}
}
if(op==0)
{cout<<"-1"<<endl;
continue;}
for(int i=0;i<op;i++)
{
if((q[i].r-q[i].l+1)==ans)
{cout<<q[i].l<<" "<<q[i].r<<endl;
break;}
}
}
return 0;
}
123