Advertisement
a_chn

Untitled

Feb 28th, 2024
807
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.65 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using Square = struct Square;
  5.  
  6. struct Square {
  7.     int x, y;
  8.  
  9.     bool operator==(const Square &other) const {
  10.         return (x == other.x) && (y == other.y);
  11.     }
  12.  
  13.     bool operator<(const Square &other) const {
  14.         return (x < other.x) || ((x == other.x) && (y < other.y));
  15.     }
  16. };
  17.  
  18. const int N1 = 1752;
  19. const int N2 = 875;
  20.  
  21. bool walls[N1][N1];
  22.  
  23. bool adjacent(const Square &first, const Square &second) {
  24.     return !walls[(first.x + second.x) / 2 + N2][(first.y + second.y) / 2 + N2];
  25. }
  26.  
  27. vector<int> x_change = {0, 0, -1, 1};
  28. vector<int> y_change = {-1, 1, 0, 0};
  29.  
  30. bool visited[N1][N1];
  31.  
  32. int its;
  33.  
  34. void flood_fill(const Square square) {
  35.     ++its;
  36.     assert(square.x + N2 >= 0 && square.y + N2 >= 0);
  37.     visited[square.x + N2][square.y + N2] = true;
  38.  
  39.     for (int index = 0; index < 4; ++index) {
  40.         Square new_square;
  41.         assert(index >= 0 && index < 4);
  42.         new_square.x = square.x + x_change[index]; new_square.y = square.y + y_change[index];
  43.        
  44.         if ((min(new_square.x, new_square.y) >= -N2) && (max(new_square.x, new_square.y) <= N2) && adjacent(square, new_square) && (visited[new_square.x + N2][new_square.y + N2] == false)) {
  45.             flood_fill(new_square);
  46.         }
  47.     }    
  48. }
  49.  
  50. int main() {
  51.     freopen("gates.in", "r", stdin);
  52.     freopen("gates.out", "w", stdout);
  53.  
  54.     int length;
  55.     cin >> length;
  56.  
  57.     for (int x = 0; x < N1; ++x) {
  58.         for (int y = 0; y < N1; ++y) {
  59.             visited[x][y] = false;
  60.             walls[x][y] = false;
  61.         }
  62.     }
  63.    
  64.     int x = N2, y = N2;
  65.     walls[x][y] = true;
  66.  
  67.     for (int _ = 0; _ < length; ++_) {
  68.         char direction;
  69.         cin >> direction;
  70.  
  71.         int start_x = x, start_y = y;
  72.  
  73.         switch (direction) {
  74.             case 'N':
  75.                 y += 2;
  76.                 break;
  77.  
  78.             case 'E':
  79.                 x += 2;
  80.                 break;
  81.  
  82.             case 'S':
  83.                 y -= 2;
  84.                 break;
  85.  
  86.             default:
  87.                 x -= 2;
  88.                 break;
  89.         }
  90.  
  91.         walls[x][y] = true;
  92.         walls[(x + start_x) / 2][(y + start_y) / 2] = true;
  93.     }
  94.  
  95.     int gates = -1;
  96.     for (float x = -N2; x <= N2; x += 1) {
  97.         for (float y = -N2; y <= N2; y += 1) {
  98.             Square square;
  99.             square.x = x;
  100.             square.y = y;
  101.  
  102.             if (!walls[square.x + N2][square.y + N2] && !visited[square.x + N2][square.y + N2]) {
  103.                 gates++;
  104.                 flood_fill(square);
  105.             }
  106.         }
  107.     }
  108.     cout << gates << "\n";
  109.     return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement