959. Regions Cut By Slashes

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 ' '.

/*
// A grid can be split into 4 small cells as belowed
// \0/
// 3X1
// /2\
*/
// Union-Find Method
int getIdx(int i, int j, int k, int n) {
    return (i * n + j) * 4 + k;
}
int find(vector<int>& roots, int i) {
    return roots[i] == i ? i : roots[i] = find(roots, roots[i]);
}
void uni(int x, int y, vector<int>& roots, vector<int>& size, int& count) {
    x = find(roots, x);
    y = find(roots, y);
    if (x == y) return;
    if (size[x] > size[y]) {
        roots[y] = x;
        size[x] += size[y];
    } else {
        roots[x] = y;
        size[y] += size[x];
    }
    --count;
}
int regionsBySlashes(vector<string>& grid) {
    int n = grid.size(), count = n * n * 4;
    vector<int> roots(count), size(count, 1);
    for (int i = 0; i < count; ++i) roots[i] = i;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i > 0) uni(getIdx(i, j, 0, n), getIdx(i - 1, j, 2, n), roots, size, count);
            if (j > 0) uni(getIdx(i, j, 3, n), getIdx(i, j - 1, 1, n), roots, size, count);
            if (grid[i][j] != '/') {
                uni(getIdx(i, j, 0, n), getIdx(i, j, 1, n), roots, size, count);
                uni(getIdx(i, j, 2, n), getIdx(i, j, 3, n), roots, size, count);
            }
            if (grid[i][j] != '\\') {
                uni(getIdx(i, j, 0, n), getIdx(i, j, 3, n), roots, size, count);
                uni(getIdx(i, j, 1, n), getIdx(i, j, 2, n), roots, size, count);
            }
        }
    }
    return count;
}

/*
Upscale the input grid to g[3 * n][3 * n] to draw lines to represent '\\' or '/'
Use DFS to connect each 0 and count the result
*/
// DFS Recursion
void dfs(vector<vector<int> >& g, int i, int j) {
    if (i < 0 || i >= g.size() || j < 0 || j >= g[0].size() || g[i][j] != 0) return;
    g[i][j] = 1; // mark 0 not to be re-calculated
    dfs(g, i + 1, j);
    dfs(g, i - 1, j);
    dfs(g, i, j + 1);
    dfs(g, i, j - 1);
}
int regionsBySlashes(vector<string>& grid) {
    int n = grid.size(), res = 0;
    vector<vector<int> > g(3 * n, vector<int>(3 * n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '/') g[3 * i][3 * j + 2] = g[3 * i + 1][3 * j + 1] = g[3 * i + 2][3 * j] = 1;
            if (grid[i][j] == '\\') g[3 * i][3 * j] = g[3 * i + 1][3 * j + 1] = g[3 * i + 2][3 * j + 2] = 1;
        }
    }
    for (int i = 0; i < 3 * n; ++i) {
        for (int j = 0; j < 3 * n; ++j) {
            if (g[i][j] == 0) {
                dfs(g, i, j);
                ++res;
            }
        }
    }
    return res;
}