Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <compare>
- #include <absl/time/time.h>
- #include <absl/time/clock.h>
- #include <sstream>
- #include <map>
- #include <regex>
- #include <absl/algorithm/container.h>
- #include <absl/strings/str_split.h>
- using namespace std;
- using namespace absl;
- struct Point {
- int x;
- int y;
- auto operator<=>(const Point &) const = default;
- auto operator+(const Point &b) {
- return Point{.x = x + b.x, .y = y + b.y};
- }
- void operator+=(const Point &b) {
- x += b.x;
- y += b.y;
- }
- struct Hash {
- size_t operator()(const Point &p) const {
- size_t rowHash = std::hash<int>()(p.x);
- size_t colHash = std::hash<int>()(p.y) << 1;
- return rowHash ^ colHash;
- }
- };
- };
- vector<Point> neighbors(const Point &p, int R, int C) {
- vector<Point> ans;
- for (const Point &d: vector<Point>{{.x=-1, .y=0},
- {.x=1, .y=0},
- {.x=0, .y=-1},
- {.x=0, .y=1}}) {
- Point n = {.x=p.x + d.x, .y=p.y + d.y};
- if (n.x >= 0 && n.x < R && n.y > 0 && n.y < C) {
- ans.push_back(n);
- }
- }
- return ans;
- }
- int main() {
- vector<vector<int>> A;
- int ans = 0;
- for (std::string line; std::getline(std::cin, line);) {
- A.push_back(vector<int>());
- for (auto c: line) {
- A.back().push_back(c - '0');
- }
- }
- int R = A.size();
- int C = A[0].size();
- vector<int> S;
- unordered_set<Point, Point::Hash> visited;
- for (int r = 0; r < R; ++r) {
- for (int c = 0; c < C; ++c) {
- Point p = {.x= r, .y=c};
- if (A[p.x][p.y] == 9 || visited.contains(p)) {
- continue;
- }
- int s = 0;
- vector<Point> to_visit = {p};
- while (!to_visit.empty()) {
- Point next = to_visit.back();
- to_visit.pop_back();
- if (visited.contains(next)) {
- continue;
- }
- visited.insert(next);
- ++s;
- for (auto n: neighbors(next, R, C)) {
- if (A[n.x][n.y] != 9) {
- to_visit.push_back(n);
- }
- }
- }
- S.push_back(s);
- }
- }
- absl::c_sort(S, [](auto a, auto b) { return a > b; });
- cout << S[0] * S[1] * S[2] << endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment