day10a.cpp (2053B)
1 #include <iostream> 2 #include <algorithm> 3 #include <set> 4 #include <string> 5 #include <string_view> 6 #include <vector> 7 using namespace std; 8 9 enum Direction { U = 0, D, R, L }; 10 Direction all_directions[] = { 11 Direction::U, Direction::D, Direction::R, Direction::L, 12 }; 13 14 pair<int, int> step(pair<int, int> p, Direction d) { 15 auto [i, j] = p; 16 17 switch (d) { 18 case Direction::U: 19 return make_pair(i-1, j); 20 case Direction::D: 21 return make_pair(i+1, j); 22 case Direction::R: 23 return make_pair(i, j+1); 24 case Direction::L: 25 return make_pair(i, j-1); 26 } 27 28 return make_pair(-999,-999); 29 } 30 31 class Board { 32 public: 33 const int out_of_bound = -1; 34 int M, N; 35 36 Board(vector<string> &lines) { 37 N = lines.size(); 38 M = 0; 39 for (string l : lines) 40 M = max(M, (int)l.size()); 41 42 cells = new int[M * N]; 43 for (int i = 0; i < N; i++) 44 for (int j = 0; j < M; j++) 45 cells[M*i + j] = lines[i][j] - '0'; 46 } 47 48 ~Board() { 49 delete []cells; 50 } 51 52 int operator[](pair<int, int> p) { 53 int c = coord(p); 54 return c == -1 ? out_of_bound : cells[c]; 55 } 56 57 private: 58 int *cells; 59 60 int coord(pair<int, int> p) { 61 auto [i, j] = p; 62 return i >= N || i < 0 || j >= M || j < 0 ? -1 : M*i + j; 63 } 64 }; 65 66 void reachable9(pair<int, int> p, Board& board, set<pair<int, int>>& s) { 67 if (board[p] == 9) { 68 s.insert(p); 69 return; 70 } 71 72 auto q = step(p, Direction::U); 73 if (board[q] == board[p]+1) 74 reachable9(q, board, s); 75 76 q = step(p, Direction::D); 77 if (board[q] == board[p]+1) 78 reachable9(q, board, s); 79 80 q = step(p, Direction::R); 81 if (board[q] == board[p]+1) 82 reachable9(q, board, s); 83 84 q = step(p, Direction::L); 85 if (board[q] == board[p]+1) 86 reachable9(q, board, s); 87 } 88 89 int main() { 90 string line; 91 vector<string> lines; 92 while (getline(cin, line)) 93 lines.push_back(line); 94 95 Board board(lines); 96 97 int tot = 0; 98 99 pair i(0, 0); 100 for (i.first = 0; i.first < board.N; i.first++) { 101 for (i.second = 0; i.second < board.M; i.second++) { 102 if (board[i] == 0) { 103 set<pair<int, int>> s; 104 reachable9(i, board, s); 105 tot += s.size(); 106 } 107 } 108 } 109 110 cout << tot << endl; 111 112 return 0; 113 }