Задача: 959. Regions Cut By Slashes
Сложность: medium

n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.

Дана сетка grid, представленная в виде строкового массива. Верните количество областей.

Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.

Пример:

Input: grid = [" /","/ "]
Output: 2

👨‍💻 Алгоритм:

1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием.

2⃣Используйте структуру объединения-поиска (DSU), чтобы найти количество связанных компонентов.

3⃣Пройдите по всем узлам и посчитайте количество корневых узлов, которые представляют количество областей.

😎 Решение:

class DSU {
public:
    vector<int> parent;
    DSU(int N) : parent(N) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unionSet(int x, int y) {
        parent[find(x)] = find(y);
    }
};

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        int N = grid.size();
        DSU dsu(4 * N * N);
        
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int root = 4 * (r * N + c);
                char val = grid[r][c];
                
                if (val != '\\') {
                    dsu.unionSet(root + 0, root + 1);
                    dsu.unionSet(root + 2, root + 3);
                }
                if (val != '/') {
                    dsu.unionSet(root + 0, root + 2);
                    dsu.unionSet(root + 1, root + 3);
                }
                
                if (r + 1 < N) {
                    dsu.unionSet(root + 3, (root + 4 * N) + 0);
                }
                if (r - 1 >= 0) {
                    dsu.unionSet(root + 0, (root - 4 * N) + 3);
                }
                if (c + 1 < N) {
                    dsu.unionSet(root + 2, (root + 4) + 1);
                }
                if (c - 1 >= 0) {
                    dsu.unionSet(root + 1, (root - 4) + 2);
                }
            }
        }
        
        int ans = 0;
        for (int x = 0; x < 4 * N * N; ++x) {
            if (dsu.find(x) == x) {
                ++ans;
            }
        }
        
        return ans;
    }
};

Ставь 👍 и забирай 📚 Базу знаний