/* This is quite inefficient, but it still gives the right answer in less than a minute (25 seconds on my old laptop). */ #include #include #include #include #include using namespace std; enum Direction { U = 0, D, R, L }; Direction all_directions[] = { Direction::U, Direction::D, Direction::R, Direction::L, }; pair step(pair p, Direction d) { auto [i, j] = p; switch (d) { case Direction::U: return make_pair(i-1, j); case Direction::D: return make_pair(i+1, j); case Direction::R: return make_pair(i, j+1); case Direction::L: return make_pair(i, j-1); } return make_pair(-999,-999); } Direction turn(Direction d) { switch (d) { case Direction::U: return Direction::R; case Direction::D: return Direction::L; case Direction::R: return Direction::D; case Direction::L: return Direction::U; } return Direction::U; } class Board { public: const char out_of_bound = '$'; int M, N; Board(vector &lines) { N = lines.size(); M = 0; for (string l : lines) M = max(M, (int)l.size()); cells = new char[M * N]; visited = new int[M * N]; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cells[M*i + j] = j < (int)lines[i].size() ? lines[i][j] : out_of_bound; visited[M*i + j] = 0; } } } ~Board() { delete []cells; delete []visited; } char operator[](pair p) { int c = coord(p); return c == -1 ? out_of_bound : cells[c]; } bool is_visited(pair p, Direction d) { return get_vmask(p) & (1 << d); } void set_visited(pair p, Direction d) { toggle_vmask(p, d); } void clear_visited() { for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) set_vmask(make_pair(i, j), 0); } bool is_obstruction(pair p) { return (*this)[p] == '#'; } void set_obstruction(pair p) { set_cell(p, '#'); } void set_clean(pair p) { set_cell(p, '.'); } private: char *cells; int *visited; int coord(pair p) { auto [i, j] = p; return i >= N || i < 0 || j >= M || j < 0 ? -1 : M*i + j; } void set_cell(pair p, char c) { int i = coord(p); cells[i] = c; } int get_vmask(pair p) { int i = coord(p); return visited[i]; } void set_vmask(pair p, int x) { int i = coord(p); visited[i] = x; } void toggle_vmask(pair p, Direction d) { int i = coord(p); visited[i] ^= 1 << d; } }; Direction guard_direction(char c) { switch (c) { case '^': return Direction::U; case 'v': return Direction::D; case '>': return Direction::R; case '<': return Direction::L; } return Direction::U; } pair, Direction> find_guard(Board &board) { pair p(0, 0); for (p.first = 0; p.first < board.N; p.first++) { for (p.second = 0; p.second < board.M; p.second++) { if (board[p] != '.' && board[p] != '#') { Direction d = guard_direction(board[p]); return make_pair(p, d); } } } return make_pair(make_pair(-999, -999), Direction::U); } bool isloop(pair i, pair p, Direction d, Board &board) { bool ret = false; board.set_obstruction(i); while (true) { auto q = step(p, d); if (board.is_visited(p, d)) { ret = true; break; } board.set_visited(p, d); if (board[q] == board.out_of_bound) break; if (board.is_obstruction(q)) { d = turn(d); } else { p = q; } } board.clear_visited(); board.set_clean(i); return ret; } int main() { string line; vector lines; while (getline(cin, line)) lines.push_back(line); Board board(lines); int tot = 0; auto [p, d] = find_guard(board); pair i(0, 0); for (i.first = 0; i.first < board.N; i.first++) for (i.second = 0; i.second < board.M; i.second++) if (board[i] == '.') tot += isloop(i, p, d, board); cout << tot << endl; return 0; }