959 Regions Cut By Slashes

959. Regions Cut By Slashes

1. Question

In a N x N gridcomposed of 1 x 1 squares, each 1 x 1 square consists of a/,\, or blank space. These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a\ is represented as"\\".)

Return the number of regions.

1. Example 1:

Input:

[
  " /",
  "/ "
]
Output: 2

Example 2:

Input:

[
  " /",
  "  "
]
Output: 1

Note:

1. 1 <= grid.length == grid[0].length <= 30

2. grid[i][j]is either'/','\', or' '.

2. Implementation

(1) Union Find

思路: 将一个square分成4个部分，将top标记为0, right标记为1, bottom标记2, left标记3. union包含两部分:

• inner connection: 一开始squaure里的四个部分是分离的，如果当前square的字符是'/', 将0，3合并，1，2合并。如果是'\', 将0, 1合并，2, 3合并。如果是“ ”, 将0，1，2，3合并

• inter connection: 将两两square合并，由于我们从左到右，上到下的顺序遍历grid，所以我们将当前square的top(0)和上面的square的bottom(2)合并，将当前square的left(3)和左边的square的right(1)合并

union结束后，计算component的数量即可

class Solution {
    public int regionsBySlashes(String[] grid) {
        int n = grid.length;
        int size = n * n * 4;

        UnionFind uf = new UnionFind(size);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0) uf.union(id(i - 1, j, 2, n), id(i, j, 0, n));

                if (j > 0) uf.union(id(i, j - 1, 1, n),id(i, j, 3, n));

                if (grid[i].charAt(j) == '/') {
                    uf.union(id(i, j, 0, n), id(i, j, 3, n));
                    uf.union(id(i, j, 1, n), id(i, j, 2, n));
                }
                else if (grid[i].charAt(j) == '\\') {
                    uf.union(id(i, j, 0, n), id(i, j, 1, n));
                    uf.union(id(i, j, 2, n), id(i, j, 3, n));
                }
                else {
                    uf.union(id(i, j, 0, n), id(i, j, 1, n));
                    uf.union(id(i, j, 2, n), id(i, j, 3, n));
                    uf.union(id(i, j, 0, n), id(i, j, 3, n));
                }
            }
        }
        return uf.count;
    }

    public int id(int row, int col, int offset, int n) {
        return (row * n + col) * 4 + offset;
    }

    class UnionFind {
        int[] root;
        int[] size;
        int count;

        public UnionFind(int n) {
            root = new int[n];
            size = new int[n];
            count = n;

            for (int i = 0; i < n; i++) {
                root[i] = i;
                size[i] = 1;
            }
        }

        public int find(int node) {
            while (node != root[node]) {
                node = root[node];
            }
            return node;
        }

        public void union(int i , int j) {
            int p = find(i);
            int q = find(j);

            if (p == q) return;

            if (size[p] < size[q]) {
                root[p] = q;
                size[q] += size[p];
            }
            else {
                root[q] = p;
                size[p] += size[q];
            }
            --count;
        }
    }
}

3. Time & Space Complexity

时间复杂度O(n^2), 空间复杂度O(n^2)