Advertisement
Guest User

Untitled

a guest
Mar 25th, 2019
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <map>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. class Sheet {
  9. private:
  10.     bool **visited;
  11.     int Y, X;
  12.  
  13.     void translate(int x_min, int y_min, map<int, set<int>> bounds);
  14.  
  15.     int free_cells();
  16.  
  17.     int visit(int x, int y);
  18.  
  19. public:
  20.     Sheet();
  21.  
  22.     int shape_size();
  23.  
  24.     ~Sheet();
  25. };
  26.  
  27. Sheet::Sheet() {
  28.     map<int, set<int>> bounds({{0, {0}}});
  29.     char move;
  30.     int x_min = 0, x_max = 0, y_min = 0, y_max = 0, x = 0, y = 0;
  31.     for (cin >> move; move != 'K'; cin >> move) {
  32.         switch (move) {
  33.             case 'N':
  34.                 y_max = max(y_max, ++y);
  35.                 break;
  36.             case 'S':
  37.                 y_min = min(y_min, --y);
  38.                 break;
  39.             case 'E':
  40.                 x_max = max(x_max, ++x);
  41.                 break;
  42.             case 'W':
  43.                 x_min = min(x_min, --x);
  44.                 break;
  45.             default:
  46.                 cerr << "UNEXPECTED CHAR INPUT: " << move << endl;
  47.                 exit(1);
  48.         }
  49.         bounds[y].insert(x);
  50.     }
  51.  
  52.     Y = y_max - y_min + 1;
  53.     X = x_max - x_min + 1;
  54.  
  55.     translate(x_min, y_min, bounds);
  56. }
  57.  
  58. void Sheet::translate(int x_min, int y_min, map<int, set<int>> bounds) {
  59.     visited = new bool *[Y];
  60.     for (int i = 0; i < Y; ++i) visited[i] = new bool[X]{};
  61.  
  62.     for (const auto &bound : bounds)
  63.         for (auto x : bound.second)
  64.             visited[bound.first - y_min][x - x_min] = true;
  65. }
  66.  
  67. Sheet::~Sheet() {
  68.     for (int y = 0; y < Y; ++y) delete[] visited[y];
  69.     delete[] visited;
  70. }
  71.  
  72. int Sheet::shape_size() { return X * Y - free_cells(); }
  73.  
  74. int Sheet::free_cells() {
  75.     int count = 0;
  76.  
  77.     for (int y : {0, Y - 1})
  78.         for (int x = 0; x < X; ++x)
  79.             if (!visited[y][x])
  80.                 count += visit(x, y);
  81.  
  82.     for (int x : {0, X - 1})
  83.         for (int y = 0; y < Y; ++y)
  84.             if (!visited[y][x])
  85.                 count += visit(x, y);
  86.  
  87.     return count;
  88. }
  89.  
  90. struct point {
  91.     int x, y;
  92. };
  93.  
  94. int Sheet::visit(int x, int y) {
  95.     int count = 0;
  96.  
  97.     visited[y][x] = true;
  98.  
  99.     queue<point> q;
  100.     q.push({x, y});
  101.     while (!q.empty()) {
  102.         count++;
  103.         point p = q.front();
  104.         q.pop();
  105.  
  106.         for (int shift : {-1, 1}) {
  107.             int x_shift = p.x + shift, y_shift = p.y + shift;
  108.  
  109.             if (x_shift >= 0 && x_shift < X && !visited[p.y][x_shift]) {
  110.                 visited[p.y][x_shift] = true;
  111.                 q.push({x_shift, p.y});
  112.             }
  113.  
  114.             if (y_shift >= 0 && y_shift < Y && !visited[y_shift][p.x]) {
  115.                 visited[y_shift][p.x] = true;
  116.                 q.push({p.x, y_shift});
  117.             }
  118.         }
  119.     }
  120.  
  121.     return count;
  122. }
  123.  
  124. int main() {
  125.     istream::sync_with_stdio(false);
  126.     ostream::sync_with_stdio(false);
  127.  
  128.     char c;
  129.     while (cin >> c) cout << Sheet().shape_size() << endl;
  130.  
  131.     return 0;
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement