#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef vector VI; typedef pair PII; #define REP(i,s,t) for(int i=(s);i<(t);i++) #define FILL(x,v) memset(x,v,sizeof(x)) const int INF = (int)1E9; #define MAXN 505 int r, c, ans; char g[MAXN][MAXN]; int deg[MAXN][MAXN]; int circle[MAXN][MAXN], C; vector adj[MAXN][MAXN], cadj[MAXN * MAXN], cspot[MAXN * MAXN]; bool isRiver(char c) { return c == '^' || c == 'v' || c == '<' || c == '>'; } VI dir[128]; int dir4[4][2] = {-1,0,1,0,0,1,0,-1}; inline bool outside(int x, int y) { return x < 0 || y < 0 || x >= r || y >= c; } void dfsCircle(int x, int y, int label) { circle[x][y] = label; REP(d,0,4) { int nx = x + dir4[d][0], ny = y + dir4[d][1]; if (outside(nx, ny)) continue; if (g[nx][ny] == '#') cspot[label].push_back(PII(nx, ny)); } char ch = g[x][y]; int nx = x + dir[ch][0], ny = y + dir[ch][1]; if (!outside(nx, ny) && isRiver(g[nx][ny]) && circle[nx][ny] == -1) dfsCircle(nx, ny, label); } void remove(map &spots, PII p) { if (--spots[p] == 0) spots.erase(p); } void solve(int x, int y, map &spots) { REP(d,0,4) { int nx = x + dir4[d][0], ny = y + dir4[d][1]; if (outside(nx, ny)) continue; if (g[nx][ny] == '#') spots[PII(nx, ny)]++; } ans = max(ans, (int)spots.size()); for (auto &nb: adj[x][y]) { solve(nb.first, nb.second, spots); } REP(d,0,4) { int nx = x + dir4[d][0], ny = y + dir4[d][1]; if (outside(nx, ny)) continue; if (g[nx][ny] == '#') remove(spots, PII(nx, ny)); } } void solveRoot(int i, map &spots) { ans = max(ans, (int)spots.size()); for (auto &nb: cadj[i]) { solve(nb.first, nb.second, spots); } } int main() { dir['^'] = VI({-1, 0}); dir['v'] = VI({1, 0}); dir['<'] = VI({0, -1}); dir['>'] = VI({0, 1}); cin >> r >> c; REP(i,0,r) cin >> g[i]; REP(i,0,r) { REP(j,0,c) { char ch = g[i][j]; if (!isRiver(ch)) continue; int ni = i + dir[ch][0], nj = j + dir[ch][1]; if (outside(ni, nj)) continue; deg[ni][nj]++; } } // Find circle roots queue q; REP(i,0,r) REP(j,0,c) if (isRiver(g[i][j]) && deg[i][j] == 0) q.push(PII(i, j)); FILL(circle, -1); while (q.size()) { int i = q.front().first, j = q.front().second; q.pop(); circle[i][j] = -2; // non-circle river char ch = g[i][j]; int ni = i + dir[ch][0], nj = j + dir[ch][1]; if (!outside(ni, nj) && isRiver(g[ni][nj])) { if (--deg[ni][nj] == 0) q.push(PII(ni, nj)); } else { circle[i][j] = -3; // non-circle roots } } // Label circles REP(i,0,r) REP(j,0,c) if (isRiver(g[i][j]) && circle[i][j] == -1) dfsCircle(i, j, C++); // Circle roots' sightseeing spots REP(i,0,C) { sort(cspot[i].begin(), cspot[i].end()); cspot[i].erase(unique(cspot[i].begin(), cspot[i].end()), cspot[i].end()); } // Build reverse edges REP(i,0,r) { REP(j,0,c) { char ch = g[i][j]; if (!isRiver(ch) || circle[i][j] != -2) continue; int ni = i + dir[ch][0], nj = j + dir[ch][1]; if (outside(ni, nj)) continue; assert(isRiver(g[ni][nj])); if (circle[ni][nj] < 0) adj[ni][nj].push_back(PII(i, j)); // regular tree node else cadj[circle[ni][nj]].push_back(PII(i, j)); // circle roots } } // Traverse circle roots' trees REP(i,0,C) { map spots; for (auto &p: cspot[i]) spots[p] = 1; solveRoot(i, spots); } // Traverse non-circle roots' trees REP(i,0,r) REP(j,0,c) if (circle[i][j] == -3) { map spots; solve(i, j, spots); } cout << ans << endl; return 0; }