Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <map>
- #include <set>
- using namespace std;
- class Sheet {
- private:
- bool **visited;
- int Y, X;
- void translate(int x_min, int y_min, map<int, set<int>> bounds);
- int free_cells();
- int visit(int x, int y);
- public:
- Sheet();
- int shape_size();
- ~Sheet();
- };
- Sheet::Sheet() {
- map<int, set<int>> bounds({{0, {0}}});
- char move;
- int x_min = 0, x_max = 0, y_min = 0, y_max = 0, x = 0, y = 0;
- for (cin >> move; move != 'K'; cin >> move) {
- switch (move) {
- case 'N':
- y_max = max(y_max, ++y);
- break;
- case 'S':
- y_min = min(y_min, --y);
- break;
- case 'E':
- x_max = max(x_max, ++x);
- break;
- case 'W':
- x_min = min(x_min, --x);
- break;
- default:
- cerr << "UNEXPECTED CHAR INPUT: " << move << endl;
- exit(1);
- }
- bounds[y].insert(x);
- }
- Y = y_max - y_min + 1;
- X = x_max - x_min + 1;
- translate(x_min, y_min, bounds);
- }
- void Sheet::translate(int x_min, int y_min, map<int, set<int>> bounds) {
- visited = new bool *[Y];
- for (int i = 0; i < Y; ++i) visited[i] = new bool[X]{};
- for (const auto &bound : bounds)
- for (auto x : bound.second)
- visited[bound.first - y_min][x - x_min] = true;
- }
- Sheet::~Sheet() {
- for (int y = 0; y < Y; ++y) delete[] visited[y];
- delete[] visited;
- }
- int Sheet::shape_size() { return X * Y - free_cells(); }
- int Sheet::free_cells() {
- int count = 0;
- for (int y : {0, Y - 1})
- for (int x = 0; x < X; ++x)
- if (!visited[y][x])
- count += visit(x, y);
- for (int x : {0, X - 1})
- for (int y = 0; y < Y; ++y)
- if (!visited[y][x])
- count += visit(x, y);
- return count;
- }
- struct point {
- int x, y;
- };
- int Sheet::visit(int x, int y) {
- int count = 0;
- visited[y][x] = true;
- queue<point> q;
- q.push({x, y});
- while (!q.empty()) {
- count++;
- point p = q.front();
- q.pop();
- for (int shift : {-1, 1}) {
- int x_shift = p.x + shift, y_shift = p.y + shift;
- if (x_shift >= 0 && x_shift < X && !visited[p.y][x_shift]) {
- visited[p.y][x_shift] = true;
- q.push({x_shift, p.y});
- }
- if (y_shift >= 0 && y_shift < Y && !visited[y_shift][p.x]) {
- visited[y_shift][p.x] = true;
- q.push({p.x, y_shift});
- }
- }
- }
- return count;
- }
- int main() {
- istream::sync_with_stdio(false);
- ostream::sync_with_stdio(false);
- char c;
- while (cin >> c) cout << Sheet().shape_size() << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement