day10b.cpp (2010B)
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 int reachable9(pair<int, int> p, Board& board) { 67 if (board[p] == 9) 68 return 1; 69 70 int ret = 0; 71 auto q = step(p, Direction::U); 72 if (board[q] == board[p]+1) 73 ret += reachable9(q, board); 74 75 q = step(p, Direction::D); 76 if (board[q] == board[p]+1) 77 ret += reachable9(q, board); 78 79 q = step(p, Direction::R); 80 if (board[q] == board[p]+1) 81 ret += reachable9(q, board); 82 83 q = step(p, Direction::L); 84 if (board[q] == board[p]+1) 85 ret += reachable9(q, board); 86 87 return ret; 88 } 89 90 int main() { 91 string line; 92 vector<string> lines; 93 while (getline(cin, line)) 94 lines.push_back(line); 95 96 Board board(lines); 97 98 int tot = 0; 99 100 pair i(0, 0); 101 for (i.first = 0; i.first < board.N; i.first++) { 102 for (i.second = 0; i.second < board.M; i.second++) { 103 if (board[i] == 0) { 104 tot += reachable9(i, board); 105 } 106 } 107 } 108 109 cout << tot << endl; 110 111 return 0; 112 }