Problem: Example

Input

9
0 0 v
1 0 >
2 0


Output

9

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

string tbl = ">v<^";

struct P{
	int id;
	int p[4];
	P(){
		id = -1;
		memset(p,-1,sizeof(p));
	}
};
P ps[3010];



int dfs(int id){
	if( id == -1 ) return 0;
	int tmp[4];
	memcpy(tmp,ps[id].p,sizeof(tmp));
	for(int i = 0 ; i < 4 ; i++){
		if(ps[id].p[i] != -1 ){
	
			assert( ps[ps[id].p[i]].p[(i+2)%4] == id );
			ps[ps[id].p[i]].p[(i+2)%4] = tmp[(i+2)%4];
		}
	}
	
	int ans = dfs(ps[id].p[ps[id].id]);
	for(int i = 0 ; i < 4 ; i++){
		if( tmp[i] != -1 ){
			assert( ps[tmp[i]].p[(i+2)%4] != id );
			ps[tmp[i]].p[(i+2)%4] = id;
		}
	}
	return ans + 1;
	
}
int main(){
	int n;
	cin >> n;
	map<int, vector< pair<int,int> > > col,row;
	for(int i = 0 ; i < n ; i++){
		int x,y;
		char c;
		cin >> x >> y >> c;
		y*= -1;
		int id = tbl.find(c);
		ps[i].id = id;
		col[x].push_back({y,i});
		row[y].push_back({x,i});
	}		
	for( auto &i : col ) sort(i.second.begin(),i.second.end());
	for( auto &i : row ) sort(i.second.begin(),i.second.end());
	
	for( auto &i : col ){
		
		auto& seq = i.second;
		{
			int prv = -1;
			for(int j = 0 ; j < seq.size() ; j++){
				ps[seq[j].second].p[1] = prv;
				prv = seq[j].second;
			}
		}
		{
			int prv = -1;
			for(int j = seq.size() - 1 ; j >= 0 ; j--){
				ps[seq[j].second].p[3] = prv;
				prv = seq[j].second;
			}
		}
	}
	
	for( auto &i : row ){
		auto& seq = i.second;
		{
			int prv = -1;
			for(int j = 0 ; j < seq.size() ; j++){
				ps[seq[j].second].p[2] = prv;
				prv = seq[j].second;
			}
		}
		{
			int prv = -1;
			for(int j = seq.size() - 1 ; j >= 0 ; j--){
				ps[seq[j].second].p[0] = prv;
				prv = seq[j].second;
			}
		}
	}
	int answer = 0;
	for(int i = 0 ; i < n ; i++){
		answer = max(answer,dfs(i));
		//cout << i << " " << dfs(i) << endl;
	}
	cout << answer << endl;
}