Problem: Example

Input

9
0 0 v
1 0 >
2 0


Output

9

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; ++ i)
using namespace std;

int x[3010],y[3010],d[3010];
int init[4][3010];
int mov[4][3010];


int main(void){
	int n;
	cin >> n;

	{
		map<char,int> dir={{'>',0},{'v',1},{'<',2},{'^',3}};
		rep(i,n){
			char tmp;
			cin >> x[i] >> y[i] >> tmp;
			d[i] = dir[tmp];
		}
	}
	

	rep(i,n){
		int u = -1, l = -1, r = -1 ,b = -1; 

		rep(j,n){
			if(j==i) continue;

			if(x[i] == x[j] and y[j] < y[i]){
				if(u == -1 or y[u] < y[j]) {
					u = j;
				}
			}

			if(x[i] == x[j] and y[i] < y[j]){
				if(b == -1 or y[j] < y[b]) {
					b = j;
				}
			}

			if(y[i] == y[j] and x[j] < x[i]){
				if(l == -1 or x[l] < x[j]) {
					l = j;
				}
			}

			if(y[i] == y[j] and x[i] < x[j]){
				if(r == -1 or x[j] < x[r]) {
					r = j;
				}
			}
		}

		init[0][i] = r;
		init[1][i] = b;
		init[2][i] = l;
		init[3][i] = u;

	}

	/*
	rep(i,n){
		cerr << i << " ";
		rep(j,4) cerr << init[j][i] << " ";
		cerr << endl;
	}
	*/

	int ans = 0;
	
	rep(s,n){
		rep(i,4)rep(j,n) mov[i][j] = init[i][j];

		int cur = s,num = 0;

		while(1){
			//cerr << cur << endl;
			if(cur == -1) break;
			num++;
			rep(i,4){
				if(mov[(i+2)%4][cur]!=-1){
					//cerr << i << " " << mov[(i+2)%4][cur] << " " << mov[i][cur] << endl;
					mov[i][mov[(i+2)%4][cur]] = mov[i][cur];
				}
			}

			int nxt = mov[d[cur]][cur];
			rep(i,4) mov[i][cur] = -1;
			cur = nxt;
		}

		ans = max(ans,num);
	}

	cout << ans << endl;
	return 0;
}