Задача: 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 {
    var parent: [Int]
    
    init(_ N: Int) {
        parent = Array(0..<N)
    }
    
    func find(_ x: Int) -> Int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    
    func union(_ x: Int, _ y: Int) {
        parent[find(x)] = find(y)
    }
}

class Solution {
    func regionsBySlashes(_ grid: [String]) -> Int {
        let N = grid.count
        let dsu = DSU(4 * N * N)
        
        for r in 0..<N {
            for c in 0..<N {
                let root = 4 * (r * N + c)
                let val = Array(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)
                }
            }
        }
        
        var ans = 0
        for x in 0..<(4 * N * N) {
            if dsu.find(x) == x {
                ans += 1
            }
        }
        
        return ans
    }
}

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