ErnestGalbrun

Untitled

Dec 8th, 2021 (edited)
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <compare>
  5. #include <absl/time/time.h>
  6. #include <absl/time/clock.h>
  7. #include <sstream>
  8. #include <map>
  9. #include <regex>
  10. #include <absl/algorithm/container.h>
  11. #include <absl/strings/str_split.h>
  12.  
  13. using namespace std;
  14. using namespace absl;
  15.  
  16.  
  17. struct Point {
  18.     int x;
  19.     int y;
  20.  
  21.     auto operator<=>(const Point &) const = default;
  22.  
  23.     auto operator+(const Point &b) {
  24.         return Point{.x = x + b.x, .y = y + b.y};
  25.     }
  26.  
  27.     void operator+=(const Point &b) {
  28.         x += b.x;
  29.         y += b.y;
  30.     }
  31.  
  32.     struct Hash {
  33.         size_t operator()(const Point &p) const {
  34.             size_t rowHash = std::hash<int>()(p.x);
  35.             size_t colHash = std::hash<int>()(p.y) << 1;
  36.             return rowHash ^ colHash;
  37.         }
  38.     };
  39. };
  40.  
  41. vector<Point> neighbors(const Point &p, int R, int C) {
  42.     vector<Point> ans;
  43.     for (const Point &d: vector<Point>{{.x=-1, .y=0},
  44.                                        {.x=1, .y=0},
  45.                                        {.x=0, .y=-1},
  46.                                        {.x=0, .y=1}}) {
  47.         Point n = {.x=p.x + d.x, .y=p.y + d.y};
  48.         if (n.x >= 0 && n.x < R && n.y > 0 && n.y < C) {
  49.             ans.push_back(n);
  50.         }
  51.     }
  52.     return ans;
  53. }
  54.  
  55. int main() {
  56.  
  57.     vector<vector<int>> A;
  58.     int ans = 0;
  59.     for (std::string line; std::getline(std::cin, line);) {
  60.         A.push_back(vector<int>());
  61.         for (auto c: line) {
  62.             A.back().push_back(c - '0');
  63.         }
  64.     }
  65.  
  66.     int R = A.size();
  67.     int C = A[0].size();
  68.  
  69.     vector<int> S;
  70.     unordered_set<Point, Point::Hash> visited;
  71.  
  72.     for (int r = 0; r < R; ++r) {
  73.         for (int c = 0; c < C; ++c) {
  74.             Point p = {.x= r, .y=c};
  75.             if (A[p.x][p.y] == 9 || visited.contains(p)) {
  76.                 continue;
  77.             }
  78.             int s = 0;
  79.             vector<Point> to_visit = {p};
  80.             while (!to_visit.empty()) {
  81.                 Point next = to_visit.back();
  82.                 to_visit.pop_back();
  83.                 if (visited.contains(next)) {
  84.                     continue;
  85.                 }
  86.                 visited.insert(next);
  87.                 ++s;
  88.                 for (auto n: neighbors(next, R, C)) {
  89.                     if (A[n.x][n.y] != 9) {
  90.                         to_visit.push_back(n);
  91.                     }
  92.                 }
  93.             }
  94.             S.push_back(s);
  95.         }
  96.     }
  97.  
  98.     absl::c_sort(S, [](auto a, auto b) { return a > b; });
  99.  
  100.     cout << S[0] * S[1] * S[2] << endl;
  101.     return 0;
  102. }
  103.  
Add Comment
Please, Sign In to add comment