#include #include #include #include #include #include #include using namespace std; const int MAXD = 19; int dx[4]{-1,0,1,0}; int dy[4]{0,1,0,-1}; template class y_combinator_result { Fun fun_; public: template explicit y_combinator_result(T &&fun): fun_(std::forward(fun)) {} template decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward(args)...); } }; template decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result>(std::forward(fun)); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int r, c; cin >> r >> c; vector g(r); vector>>> to(r); for(auto& x: to) { x.resize(c); for(auto& y: x) { y.resize(MAXD); fill(y.begin(), y.end(), make_pair(-1, -1)); } } for(int i = 0; i < r; i++) { cin >> g[i]; for(int j = 0; j < c; j++) { if(g[i][j] == '^') to[i][j][0] = make_pair(i-1, j); else if(g[i][j] == '<') to[i][j][0] = make_pair(i, j-1); else if(g[i][j] == 'v') to[i][j][0] = make_pair(i+1, j); else if(g[i][j] == '>') to[i][j][0] = make_pair(i, j+1); else to[i][j][0] = make_pair(i, j); } } for(int d = 1; d < MAXD; d++) for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) { auto orig = to[i][j][d-1]; if(orig.first < 0 || orig.first >= r || orig.second < 0 || orig.second >= c) to[i][j][d] = orig; else to[i][j][d] = to[orig.first][orig.second][d-1]; } vector> cycleidx(r); auto getpointcycleidx = [&](int x, int y) -> int { auto cand = to[x][y][MAXD-1]; if(cand.first < 0 || cand.first >= r || cand.second < 0 || cand.second >= c) return -1 - (cand.first + 1) * 1000 - cand.second; return cycleidx[cand.first][cand.second]; }; for(auto& x: cycleidx) { x.resize(c); fill(x.begin(), x.end(), -1); } vector> dp(r); for(auto& x: dp) { x.resize(c); fill(x.begin(), x.end(), -1); } int ret = 0; { int numcycles = 0; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) { if(g[i][j] == '.' || g[i][j] == '#') { dp[i][j] = 0; cycleidx[i][j] = numcycles++; continue; } auto [destx, desty] = to[i][j][MAXD-1]; if(destx < 0 || destx >= r || desty < 0 || desty >= c || g[destx][desty] == '.' || g[destx][desty] == '#') continue; if(cycleidx[destx][desty] >= 0) continue; vector> seen; int cyclesz = 0; while(cycleidx[destx][desty] < 0) { cyclesz++; for(int k = 0; k < 4; k++) { int nx = destx + dx[k]; int ny = desty + dy[k]; if(nx >= 0 && nx < r && ny >= 0 && ny < c && g[nx][ny] == '#') seen.emplace_back(nx, ny); } cycleidx[destx][desty] = numcycles; auto nxt = to[destx][desty][0]; destx = nxt.first; desty = nxt.second; } numcycles++; sort(seen.begin(), seen.end()); seen.erase(unique(seen.begin(), seen.end()), seen.end()); ret = max(ret, (int)seen.size()); for(int k = 0; k < cyclesz; k++) { dp[destx][desty] = seen.size(); auto nxt = to[destx][desty][0]; destx = nxt.first; desty = nxt.second; } } } vector> disttocycle(r); for(auto& x: disttocycle) { x.resize(c); fill(x.begin(), x.end(), -1); } auto dfsfordist = y_combinator([&](auto self, int x, int y) -> int { if(x < 0 || x >= r || y < 0 || y >= c) return 0; if(disttocycle[x][y] >= 0) return disttocycle[x][y]; if(cycleidx[x][y] >= 0) return disttocycle[x][y] = 0; if(g[x][y] == '#' || g[x][y] == '.') return disttocycle[x][y] = 0; int nxtx = x; int nxty = y; if(g[x][y] == '^') nxtx--; else if(g[x][y] == '<') nxty--; else if(g[x][y] == 'v') nxtx++; else if(g[x][y] == '>') nxty++; else assert(false); return disttocycle[x][y] = 1 + self(nxtx, nxty); }); for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) dfsfordist(i, j); auto dfsfordp = y_combinator([&](auto self, int x, int y) -> int { if(x < 0 || x >= r || y < 0 || y >= c) return 0; if(dp[x][y] >= 0) return dp[x][y]; if(g[x][y] == '#' || g[x][y] == '.') return dp[x][y] = 0; int nxtx = x; int nxty = y; if(g[x][y] == '^') nxtx--; else if(g[x][y] == '<') nxty--; else if(g[x][y] == 'v') nxtx++; else if(g[x][y] == '>') nxty++; else assert(false); dp[x][y] = self(nxtx, nxty); // check for adjacent which are seen here for(int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if(nx < 0 || nx >= r || ny < 0 || ny >= c || g[nx][ny] != '#') continue; bool valid = true; for(int kk = 0; kk < 4 && valid; kk++) { int candx = nx + dx[kk]; int candy = ny + dy[kk]; if(candx < 0 || candx >= r || candy < 0 || candy >= c || g[candx][candy] == '.' || g[candx][candy] == '#') continue; if(disttocycle[candx][candy] >= disttocycle[x][y]) continue; if(getpointcycleidx(candx, candy) != getpointcycleidx(x, y)) continue; if(disttocycle[candx][candy] == 0) { valid = false; continue; } int travel = disttocycle[x][y] - disttocycle[candx][candy]; int nowx = x; int nowy = y; for(int a = 0; a < MAXD; a++) if(travel & (1 << a)) { auto go = to[nowx][nowy][a]; nowx = go.first; nowy = go.second; } if(nowx != candx || nowy != candy) continue; valid = false; } dp[x][y] += valid; } return dp[x][y]; }); for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) ret = max(ret, dfsfordp(i, j)); cout << ret << "\n"; }