#include #include #include #include #include constexpr int drs[] = {1, 0, -1, 0}; constexpr int dcs[] = {0, 1, 0, -1}; struct Solver { Solver() { std::cin >> r_ >> c_; nodes_ = r_ * c_; grid_.resize(r_); for (auto& row : grid_) { std::cin >> row; } buildGraph(); findChains(); findCycles(); buildChains(); buildSparseTable(); cache_.assign(nodes_, -1); ans_ = 0; for (int32_t u = 0; u < nodes_; ++u) { ans_ = std::max(ans_, findAnswer(u)); } } void buildGraph() { edge_.assign(nodes_, -1); inDeg_.assign(nodes_, 0); reverseGraph_.resize(nodes_); // Find the cycles by top sorting + marking chains for (int32_t i = 0; i < r_; ++i) { for (int32_t j = 0; j < c_; ++j) { auto [dr, dc] = getMove(grid_[i][j]); if ((dr | dc) != 0 && inBounds(i + dr, j + dc)) { int32_t cur = makeNode(i, j); int32_t nxt = makeNode(i + dr, j + dc); edge_[cur] = nxt; reverseGraph_[nxt].push_back(cur); ++inDeg_[nxt]; } } } } void findChains() { std::vector curDeg = inDeg_; std::queue q; for (int32_t u = 0; u < nodes_; ++u) { if (isSpace(u) && curDeg[u] == 0) { q.push(u); } } inChain_.assign(nodes_, false); while (!q.empty()) { int32_t u = q.front(); q.pop(); inChain_[u] = true; if (edge_[u] != -1 && --curDeg[edge_[u]] == 0) { q.push(edge_[u]); } } } void addAttractions(std::vector& attractions, int32_t u) const { int32_t i = u / c_; int32_t j = u % c_; for (auto d = 0; d < 4; ++d) { int32_t ni = i + drs[d]; int32_t nj = j + dcs[d]; if (inBounds(ni, nj) && grid_[ni][nj] == '#') { attractions.push_back(makeNode(ni, nj)); } } }; void findCycles() { cycleId_.assign(nodes_, -1); for (int32_t u = 0; u < nodes_; ++u) { if (edge_[u] != -1 && !inChain_[u] && cycleId_[u] == -1) { int32_t id = attractions_.size(); attractions_.emplace_back(); std::vector& curAttractions = attractions_.back(); int32_t cur = u; do { cycleId_[cur] = id; addAttractions(curAttractions, cur); cur = edge_[cur]; } while (cur != u); std::sort(curAttractions.begin(), curAttractions.end()); curAttractions.erase(std::unique(curAttractions.begin(), curAttractions.end()), curAttractions.end()); } } } void dfsChain(int32_t u) { for (int32_t v : reverseGraph_[u]) { if (inChain_[v]) { depth_[v] = depth_[u] + 1; cycleId_[v] = cycleId_[u]; dfsChain(v); } } } void buildChains() { depth_.assign(nodes_, -1); for (int32_t u = 0; u < nodes_; ++u) { if (isSpace(u) && (!inChain_[u] || !isSpace(edge_[u]))) { depth_[u] = 0; dfsChain(u); } } } void buildSparseTable() { int32_t log = 1; while ((1 << log) <= nodes_) { ++log; } sparseTable_.resize(log); sparseTable_[0] = edge_; for (int j = 0; j + 1 < log; ++j) { sparseTable_[j + 1] = sparseTable_[j]; for (int32_t u = 0; u < nodes_; ++u) { if (sparseTable_[j][u] != -1) { sparseTable_[j + 1][u] = sparseTable_[j][sparseTable_[j][u]]; } } } } int32_t findAnswer(int32_t u) const { if (!isSpace(u)) { return 0; } if (!inChain_[u]) { return attractions_[cycleId_[u]].size(); } if (cache_[u] != -1) { return cache_[u]; } // for each attraction next to us that we will not reach in the future // add to the count int32_t& res = cache_[u]; res = findAnswer(edge_[u]); std::vector nearby; addAttractions(nearby, u); for (int32_t spot : nearby) { bool reachLater = cycleId_[u] != -1 ? fastContains(attractions_[cycleId_[u]], spot) : false; for (int d = 0; !reachLater && d < 4; ++d) { int32_t ni = spot / c_ + drs[d]; int32_t nj = spot % c_ + dcs[d]; int32_t node = makeNode(ni, nj); reachLater |= inBounds(ni, nj) && isSpace(node) && canReach(u, node); } if (!reachLater) { ++res; } } return res; } std::pair getMove(char c) const { switch (c) { case '^': return {-1, 0}; case '>': return {0, +1}; case 'v': return {+1, 0}; case '<': return {0, -1}; default: return {0, 0}; } } int32_t makeNode(int32_t i, int32_t j) const { return c_ * i + j; } bool inBounds(int32_t i, int32_t j) const { return 0 <= i && i < r_ && 0 <= j && j < c_; } bool isSpace(int32_t u) const { return 0 <= u && u < r_ * c_ && getMove(grid_[u / c_][u % c_]) != std::pair(0, 0); } template static bool fastContains(const std::vector& data, T val) { auto it = std::lower_bound(data.begin(), data.end(), val); return it != data.end() && *it == val; } int32_t walk(int32_t u, int32_t dep) const { for (int32_t j = 0; u != -1 && j < sparseTable_.size(); ++j) { if ((dep & (1 << j)) > 0) { u = sparseTable_[j][u]; } } return u; } bool canReach(int32_t u, int32_t v) const { if (u == v || !inChain_[u] || !inChain_[v] || cycleId_[u] != cycleId_[v] || depth_[u] <= depth_[v]) { return false; } int32_t nxt = walk(u, depth_[u] - depth_[v]); return nxt == v; } int32_t r_; int32_t c_; int32_t nodes_; std::vector edge_; std::vector inDeg_; std::vector cycleId_; std::vector depth_; mutable std::vector cache_; std::vector inChain_; std::vector grid_; std::vector> reverseGraph_; std::vector> sparseTable_; // TODO: look up the right name for this. std::vector> attractions_; int32_t ans_; }; template void dumpMatrix(int32_t r, int32_t c, const std::vector& data) { for (int32_t i = 0; i < r; ++i) { for (int32_t j = 0; j < c; ++j) { T x = data[c * i + j]; if (x < 0) { std::cerr << "-"; } else { std::cerr << x; } } std::cerr << std::endl; } std::cerr << std::endl; } int main() { Solver solver; /* dumpMatrix(solver.r_, solver.c_, solver.inChain_); dumpMatrix(solver.r_, solver.c_, solver.depth_); dumpMatrix(solver.r_, solver.c_, solver.cache_); */ std::cout << solver.ans_ << '\n'; return 0; }