999. Regions Cut By Slashes

• Difficulty: Medium

• Topics: Depth-first Search, Union Find, Graph

• Similar Questions:

Problem:

In a N x N grid composed 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.

Example 1:

Input:
[
  " /",
  "/ "
]
Output: 2
Explanation: The 2x2 grid is as follows:

Example 2:

Input:
[
  " /",
  "  "
]
Output: 1
Explanation: The 2x2 grid is as follows:

Example 3:

Input:
[
  "\\/",
  "/\\"
]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
The 2x2 grid is as follows:

Example 4:

Input:
[
  "/\\",
  "\\/"
]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)
The 2x2 grid is as follows:

Example 5:

Input:
[
  "//",
  "/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:

Note:

1. 1 <= grid.length == grid[0].length <= 30
2. grid[i][j] is either '/', '\', or ' '.

Solutions:

class Solution {
public:
    class UF {
    public:
        bool exist(int a) {
            return parents.count(a) > 0;
        }

        int getSize() {
            return size;
        }

        void add(int a) {
            parents[a] = a;
            ++size;
        }

        void connect(int a, int b) {
            int rootA = find(a);
            int rootB = find(b);

            if (rootA != rootB) {
                parents[rootA] = rootB;
                --size;
            }
        }

        int find(int x) {
            if (parents.count(x) == 0) {
                parents[x] = x;
                ++size;
            }

            if (parents[x] != x) {
                parents[x] = find(parents[x]);
            }
            return parents[x];
        }
    private:
        map<int, int> parents;
        int size = 0;
    };

    int regionsBySlashes(vector<string>& grid) {
        int m = grid.size();
        if (m == 0) return 0;
        int n = grid[0].size();
        if (n == 0) return 0;
        UF uf;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                char c = grid[i][j];
                int gridId = i * n + j;
                if (c == '/') {
                    uf.connect(gridId * 4 + 0, gridId * 4 + 1); // left and up
                    uf.connect(gridId * 4 + 2, gridId * 4 + 3); // right and down
                } else if (c == '\\') {
                    uf.connect(gridId * 4 + 0, gridId * 4 + 3); // left and down
                    uf.connect(gridId * 4 + 1, gridId * 4 + 2); // up and right
                } else {
                    uf.connect(gridId * 4 + 0, gridId * 4 + 1);
                    uf.connect(gridId * 4 + 0, gridId * 4 + 2);
                    uf.connect(gridId * 4 + 0, gridId * 4 + 3); 
                }

                if (i > 0) {
                    uf.connect(gridId * 4 + 1, ((i - 1) * n + j) * 4 + 3);
                }
                if (i < m - 1) {
                    uf.connect(gridId * 4 + 3, ((i + 1) * n + j) * 4 + 1);
                }
                if (j > 0) {
                    uf.connect(gridId * 4 + 0, (i * n + j - 1) * 4 + 2);
                }
                if (j < n - 1) {
                    uf.connect(gridId * 4 + 2, (i * n + j + 1) * 4 + 0);
                }
            }
        }

        return uf.getSize();
    }
};