Problem: Example

Input

9
0 0 v
1 0 >
2 0


Output

9

Solution (in CPP):

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

int solve(int x, int y, vector<set<int>>& vx, vector<set<int>>& vy, char d, vector<vector<char>> const& dd) {
    if(d == '>') {
        auto it = vy[y].upper_bound(x);
        if(it == vy[y].end()) {
            return 1;
        }
        int nx = (*it);
        char nd = dd[*it][y];
        vy[y].erase(it);
        vx[nx].erase(y);
        return solve(nx, y, vx, vy, nd, dd) + 1;
    } else if(d == '<') {
        auto it = vy[y].lower_bound(x);
        if(it == vy[y].begin()) {
            return 1;
        }
        int nx = *(--it);
        char nd = dd[nx][y];
        vy[y].erase(it);
        vx[nx].erase(y);
        return solve(nx, y, vx, vy, nd, dd) + 1;
    } else if(d == 'v') {
        auto it = vx[x].upper_bound(y);
        if(it == vx[x].end()) {
            return 1;
        }
        int ny = *it;
        char nd = dd[x][ny];
        vx[x].erase(ny);
        vy[ny].erase(x);
        return solve(x, ny, vx, vy, nd, dd) + 1;
    } else {
        auto it = vx[x].lower_bound(y);
        if(it == vx[x].begin()) {
            return 1;
        }
        int ny = *(--it);
        char nd = dd[x][ny];
        vx[x].erase(ny);
        vy[ny].erase(x);
        return solve(x, ny, vx, vy, nd, dd) + 1;
    }
}

int main() {
    int n;
    cin >> n;
    using data = tuple<int, int, char>;
    vector<int> x(n), y(n);
    vector<char> d(n);
    vector<int> xs, ys;
    for(int i=0; i<n; ++i) {
        cin >> x[i] >> y[i] >> d[i];
        xs.push_back(x[i]);
        ys.push_back(y[i]);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    for(int i=0; i<n; ++i) {
        x[i] = lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin();
        y[i] = lower_bound(ys.begin(), ys.end(), y[i]) - ys.begin();
    }
    vector<vector<char>> dd(xs.size(), vector<char>(ys.size()));
    for(int i=0; i<n; ++i) {
        dd[x[i]][y[i]] = d[i];
    }
    vector<set<int>> vx(xs.size());
    vector<set<int>> vy(ys.size());
    for(int i=0; i<n; ++i) {
        vx[x[i]].insert(y[i]);
        vy[y[i]].insert(x[i]);
    }
    int res = 0;
    for(int i=0; i<n; ++i) {
        auto vxx = vx;
        auto vyy = vy;
        vxx[x[i]].erase(y[i]);
        vyy[y[i]].erase(x[i]);
        res = max(res, solve(x[i], y[i], vxx, vyy, d[i], dd));
    }
    cout << res << endl;
}