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