Submission #2559992

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int N, X[3009], Y[3009]; char c[3009], p[3009][3009]; vector<int>x, y;
set<int>DX[3009], DY[3009];

void dels(int px, int py) {
	DX[px].erase(py);
	DY[py].erase(px);
}

int solve(int pos) {
	for (int i = 0; i < N; i++) { DX[i].clear(); DY[i].clear(); }
	for (int i = 1; i <= N; i++) { DX[X[i]].insert(Y[i]); DY[Y[i]].insert(X[i]); }

	int cnt = 0, vx = X[pos], vy = Y[pos]; char dir = c[pos];

	while (true) {
		dels(vx, vy); dir = p[vx][vy]; cnt++;
		if (dir == '<' || dir == '>') {
			auto itr = DX[vx].lower_bound(vy);
			if (dir == '<') {
				if (itr == DX[vx].begin()) break;
				itr--;
			}
			if (itr == DX[vx].end()) break;
			vy = *itr;
		}
		else {
			auto itr = DY[vy].lower_bound(vx);
			if (dir == '^') {
				if (itr == DY[vy].begin()) break;
				itr--;
			}
			if (itr == DY[vy].end()) break;
			vx = *itr;
		}
	}
	return cnt;
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> X[i] >> Y[i] >> c[i]; swap(X[i], Y[i]);
		x.push_back(X[i]);
		y.push_back(Y[i]);
	}
	sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
	sort(y.begin(), y.end()); y.erase(unique(y.begin(), y.end()), y.end());
	
	for (int i = 1; i <= N; i++) {
		X[i] = lower_bound(x.begin(), x.end(), X[i]) - x.begin();
		Y[i] = lower_bound(y.begin(), y.end(), Y[i]) - y.begin();
		p[X[i]][Y[i]] = c[i];
	}
	int maxn = 0;
	for (int i = 1; i <= N; i++) {
		maxn = max(maxn, solve(i));
	}
	cout << maxn << endl;
	return 0;
}

Submission Info

Judge Result