Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using Square = struct Square;
- struct Square {
- int x, y;
- bool operator==(const Square &other) const {
- return (x == other.x) && (y == other.y);
- }
- bool operator<(const Square &other) const {
- return (x < other.x) || ((x == other.x) && (y < other.y));
- }
- };
- const int N1 = 1752;
- const int N2 = 875;
- bool walls[N1][N1];
- bool adjacent(const Square &first, const Square &second) {
- return !walls[(first.x + second.x) / 2 + N2][(first.y + second.y) / 2 + N2];
- }
- vector<int> x_change = {0, 0, -1, 1};
- vector<int> y_change = {-1, 1, 0, 0};
- bool visited[N1][N1];
- int its;
- void flood_fill(const Square square) {
- ++its;
- assert(square.x + N2 >= 0 && square.y + N2 >= 0);
- visited[square.x + N2][square.y + N2] = true;
- for (int index = 0; index < 4; ++index) {
- Square new_square;
- assert(index >= 0 && index < 4);
- new_square.x = square.x + x_change[index]; new_square.y = square.y + y_change[index];
- 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)) {
- flood_fill(new_square);
- }
- }
- }
- int main() {
- freopen("gates.in", "r", stdin);
- freopen("gates.out", "w", stdout);
- int length;
- cin >> length;
- for (int x = 0; x < N1; ++x) {
- for (int y = 0; y < N1; ++y) {
- visited[x][y] = false;
- walls[x][y] = false;
- }
- }
- int x = N2, y = N2;
- walls[x][y] = true;
- for (int _ = 0; _ < length; ++_) {
- char direction;
- cin >> direction;
- int start_x = x, start_y = y;
- switch (direction) {
- case 'N':
- y += 2;
- break;
- case 'E':
- x += 2;
- break;
- case 'S':
- y -= 2;
- break;
- default:
- x -= 2;
- break;
- }
- walls[x][y] = true;
- walls[(x + start_x) / 2][(y + start_y) / 2] = true;
- }
- int gates = -1;
- for (float x = -N2; x <= N2; x += 1) {
- for (float y = -N2; y <= N2; y += 1) {
- Square square;
- square.x = x;
- square.y = y;
- if (!walls[square.x + N2][square.y + N2] && !visited[square.x + N2][square.y + N2]) {
- gates++;
- flood_fill(square);
- }
- }
- }
- cout << gates << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement