Задача: 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 {
    constructor(N) {
        this.parent = Array.from({ length: N }, (_, i) => i);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        this.parent[this.find(x)] = this.find(y);
    }
}

var regionsBySlashes = function(grid) {
    const N = grid.length;
    const dsu = new DSU(4 * N * N);

    for (let r = 0; r < N; r++) {
        for (let c = 0; c < N; c++) {
            const root = 4 * (r * N + c);
            const val = grid[r][c];
            
            if (val !== '\\') {
                dsu.union(root + 0, root + 1);
                dsu.union(root + 2, root + 3);
            }
            if (val !== '/') {
                dsu.union(root + 0, root + 2);
                dsu.union(root + 1, root + 3);
            }

            if (r + 1 < N) {
                dsu.union(root + 3, (root + 4 * N) + 0);
            }
            if (r - 1 >= 0) {
                dsu.union(root + 0, (root - 4 * N) + 3);
            }
            if (c + 1 < N) {
                dsu.union(root + 2, (root + 4) + 1);
            }
            if (c - 1 >= 0) {
                dsu.union(root + 1, (root - 4) + 2);
            }
        }
    }

    let ans = 0;
    for (let x = 0; x < 4 * N * N; x++) {
        if (dsu.find(x) === x) {
            ans++;
        }
    }

    return ans;
};

овых

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