day06a.cpp (2738B)
1 #include <iostream> 2 #include <algorithm> 3 #include <string> 4 #include <string_view> 5 #include <vector> 6 using namespace std; 7 8 enum class Direction { U, D, R, L }; 9 Direction all_directions[] = { 10 Direction::U, Direction::D, Direction::R, Direction::L, 11 }; 12 13 pair<int, int> step(pair<int, int> p, Direction d) { 14 auto [i, j] = p; 15 16 switch (d) { 17 case Direction::U: 18 return make_pair(i-1, j); 19 case Direction::D: 20 return make_pair(i+1, j); 21 case Direction::R: 22 return make_pair(i, j+1); 23 case Direction::L: 24 return make_pair(i, j-1); 25 } 26 27 return make_pair(-999,-999); 28 } 29 30 Direction turn(Direction d) { 31 switch (d) { 32 case Direction::U: 33 return Direction::R; 34 case Direction::D: 35 return Direction::L; 36 case Direction::R: 37 return Direction::D; 38 case Direction::L: 39 return Direction::U; 40 } 41 42 return Direction::U; 43 } 44 45 class Board { 46 public: 47 const char out_of_bound = '$'; 48 int M, N; 49 50 Board(vector<string> &lines) { 51 N = lines.size(); 52 M = 0; 53 for (string l : lines) 54 M = max(M, (int)l.size()); 55 cells = new char[M * N]; 56 for (int i = 0; i < N; i++) 57 for (int j = 0; j < M; j++) 58 cells[M*i + j] = j < (int)lines[i].size() ? 59 lines[i][j] : out_of_bound; 60 } 61 62 ~Board() { 63 delete []cells; 64 } 65 66 char operator[](pair<int, int> p) { 67 int c = coord(p); 68 return c == -1 ? out_of_bound : cells[c]; 69 } 70 71 bool is_obstruction(pair<int, int> p) { 72 return (*this)[p] == '#'; 73 } 74 75 bool is_visited(pair<int, int> p) { 76 return (*this)[p] == 'x'; 77 } 78 79 void set_visited(pair<int, int> p) { 80 int c = coord(p); 81 cells[c] = 'x'; 82 } 83 84 private: 85 char *cells; 86 87 int coord(pair<int, int> p) { 88 auto [i, j] = p; 89 return i >= N || i < 0 || j >= M || j < 0 ? -1 : M*i + j; 90 } 91 }; 92 93 Direction guard_direction(char c) { 94 switch (c) { 95 case '^': 96 return Direction::U; 97 case 'v': 98 return Direction::D; 99 case '>': 100 return Direction::R; 101 case '<': 102 return Direction::L; 103 } 104 105 return Direction::U; 106 } 107 108 pair<pair<int, int>, Direction> find_guard(Board &board) { 109 pair<int, int> p(0, 0); 110 for (p.first = 0; p.first < board.N; p.first++) { 111 for (p.second = 0; p.second < board.M; p.second++) { 112 if (board[p] != '.' && board[p] != '#') { 113 Direction d = guard_direction(board[p]); 114 return make_pair(p, d); 115 } 116 } 117 } 118 119 return make_pair(make_pair(-999, -999), Direction::U); 120 } 121 122 int main() { 123 string line; 124 vector<string> lines; 125 while (getline(cin, line)) 126 lines.push_back(line); 127 128 Board board(lines); 129 130 int tot = 1; 131 auto [p, d] = find_guard(board); 132 board.set_visited(p); 133 134 while (true) { 135 auto q = step(p, d); 136 if (board[q] == board.out_of_bound) 137 break; 138 if (board.is_obstruction(q)) { 139 d = turn(d); 140 } else { 141 p = q; 142 if (!board.is_visited(p)) { 143 board.set_visited(p); 144 tot++; 145 } 146 } 147 } 148 149 cout << tot << endl; 150 151 return 0; 152 }