1296C Yet Another Walking Robot （Codeforces）（map）

Yet Another Walking Robot

題目連結

題意：輸入一段路徑，輸出最短的重複段。

思路：每走一步将到達的點存入map，進行判重，并儲存最小值； 

#include<iostream>
#include<map>
using namespace std;
struct node{
	int x,y;
	friend bool operator<(node a,node b){
		return a.x==b.x?a.y<b.y:a.x<b.x;
	}
};
long long minn;
 
int main(){
	int T;
	cin>>T;
	while(T--){
		int n,x=0,y=0,l,ll,r,rr,flag=0;
		node e;
		map<node,int> ma;
		minn=0x3f3f3f3f;
		e.x=x;
		e.y=y;
		ma[e]=-1;
		string s;
		cin>>n;
		flag=0;
			cin>>s;
		for(int i=1;i<=n;i++){
			
			if(s[i-1]=='L'){//移動
				x--;
				e.x=x;
				e.y=y;
				if(ma[e]!=0){
				flag=1;
				if(ma[e]!=-1){
					l=ma[e]+1;
				}
				else l=1;
				r=i;
				if(minn>(r-l+1)){
					ll=l;
					rr=r;
					minn=(r-l+1);//更新最小值
				}
			}
			 ma[e]=i;//将此時經過的點進行儲存。
			}
			if(s[i-1]=='R'){
				x++;
				e.x=x;
				e.y=y;
				if(ma[e]!=0){
				flag=1;
				if(ma[e]!=-1){
					l=ma[e]+1;
				}//不是原點，（其實把原點值設為1，其他點值設為i+1更好。。。）
				else l=1;
				r=i;
				if(minn>(r-l+1)){
					ll=l;
					rr=r;
					minn=(r-l+1);
				}
			}
			ma[e]=i;
			}
			if(s[i-1]=='U'){
				y++;
				e.x=x;
				e.y=y;
				if(ma[e]!=0){
				flag=1;
				if(ma[e]!=-1){
					l=ma[e]+1;
				}
				else l=1;
				r=i;
				if(minn>(r-l+1)){
					ll=l;
					rr=r;
					minn=(r-l+1);
				}
			}
			 ma[e]=i;
			}
			if(s[i-1]=='D'){
				y--;
				e.x=x;
				e.y=y;
				if(ma[e]!=0){
				flag=1;
				if(ma[e]!=-1){
					l=ma[e]+1;
				}
				else l=1;
				r=i;
				if(minn>(r-l+1)){
					ll=l;
					rr=r;
					minn=(r-l+1);
				}	
			}
			ma[e]=i;
			}
//			cout<<x<<"  "<<y<<"  "<<ma[e]<<" "<<ll<<" "<<rr<<endl;
		}
		if(flag) cout<<ll<<" "<<rr<<endl;
		else cout<<"-1\n";
	}
	return 0;
}