Medium
Related Topics: Array / Hash Table / DFS / BFS / Union Find Matrix
LeetCode Source

解題想法

計算給定的網格中有多少個不同的區域。

網格中的每個單元格可能包含斜線 / 或 \ 或者沒有任何斜線。

這些斜線會劃分單元格，影響區域的數量。

我們使用了 Union-Find 資料結構來解決這個問題。

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n^2)

Python

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        def find_set(root_index):
            if parent[root_index] != root_index:
                parent[root_index] = find_set(parent[root_index])
            return parent[root_index]

        def union_sets(set_a, set_b):
            root_a, root_b = find_set(set_a), find_set(set_b)
            if root_a != root_b:
                parent[root_a] = root_b
                nonlocal region_count
                region_count -= 1

        n = len(grid)
        region_count = n * n * 4
        parent = list(range(region_count))

        for i, row in enumerate(grid):
            for j, value in enumerate(row):
                cell_index = i * n + j
                if i < n - 1:
                    union_sets(4 * cell_index + 2, 4 * (cell_index + n))
                if j < n - 1:
                    union_sets(4 * cell_index + 1, 4 * (cell_index + 1) + 3)

                if value == '/':
                    union_sets(4 * cell_index, 4 * cell_index + 3)
                    union_sets(4 * cell_index + 1, 4 * cell_index + 2)
                elif value == '\\':
                    union_sets(4 * cell_index, 4 * cell_index + 1)
                    union_sets(4 * cell_index + 2, 4 * cell_index + 3)
                else:
                    union_sets(4 * cell_index, 4 * cell_index + 1)
                    union_sets(4 * cell_index + 1, 4 * cell_index + 2)
                    union_sets(4 * cell_index + 2, 4 * cell_index + 3)
        return region_count

C++

class Solution {
public:
    vector<int> parent; 
    int regionsCount;   
    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        regionsCount = n * n * 4;
        parent.resize(regionsCount);
        for (int i = 0; i < regionsCount; ++i) parent[i] = i;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int rootIndex = i * n + j;
                if (i < n - 1) {
                    merge(rootIndex * 4 + 2, (rootIndex + n) * 4);
                }
                if (j < n - 1) {
                    merge(rootIndex * 4 + 1, (rootIndex + 1) * 4 + 3);
                }
                char value = grid[i][j];
                if (value == '/') {
                    merge(rootIndex * 4, rootIndex * 4 + 3);
                    merge(rootIndex * 4 + 1, rootIndex * 4 + 2);
                } else if (value == '\\') {
                    merge(rootIndex * 4, rootIndex * 4 + 1);
                    merge(rootIndex * 4 + 2, rootIndex * 4 + 3);
                } else {
                    merge(rootIndex * 4, rootIndex * 4 + 1);
                    merge(rootIndex * 4 + 1, rootIndex * 4 + 2);
                    merge(rootIndex * 4 + 2, rootIndex * 4 + 3);
                }
            }
        }

        return regionsCount;
    }

    void merge(int nodeA, int nodeB) {
        int parentA = find(nodeA);
        int parentB = find(nodeB);
        if (parentA != parentB) {
            parent[parentA] = parentB;
            --regionsCount;
        }
    }

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